DFS之剪枝与优化

AcWing 165. 小猫爬山

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

int n, m;
int w[N], sum[N];
int ans = 0x3f3f3f3f;

bool cmp(int a, int b) {
   
    return a > b;
}

void dfs(int u, int len) {
   
    
    if (len > ans) return ;
    
    if (u == n) {
   
        ans = min(ans, len);
        return ;
    }
    
    
    
    bool flag = true;
    for (int i = 0; i < len; i ++ ) {
   
        if (w[u] + sum[i] <= m) {
   
            sum[i] += w[u];
            flag = false;
            dfs(u + 1, len);
            sum[i] -= w[u];
            flag = true;
        }
    }
    
    if (flag) {
   
        sum[len] += w[u];
        dfs(u + 1, len + 1);
        sum[len] -= w[u];
    }
}

int main() {
   
    
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++ ) cin >> w[i];
    
    sort(w, w + n, cmp);
    
    dfs(0, 0);
    
    cout << ans;
    return 0;
}

166. 数独

AcWing 167. 木棒

#include <bits/stdc++.h>
using namespace std;

const int N = 70;
int w[N];
int len, n, sum;
bool st[N];

bool cmp(int a, int b) {
   
    return a > b;
}

//u : 表示一个len一个len用，检查是否刚好用了u个木棒后可以接完木棍， cnt表示 一整根木棍接好， start用来控制组合
bool dfs(int u, int cnt, int start) {
   
    
    if(u*len == sum) return true;
    if(cnt == len) return dfs(u+1, 0, 0);
    
    for(int i=start; i<n; i++) {
   
        if(!st[i] && cnt+w[i]<=len) {
   
            st[i] = true;
            if(dfs(u, cnt+w[i], i+1)) return true;
            st[i] = false;
            
            if(!cnt || cnt+w[i]==len) return false;
            
            int j = i;
            while(j<n && w[j]==w[i]) j++;
            i = j-1;
        }
    }
    
    return false;
}

int main() {
   
    
    while(cin >> n, n) {
   
        
        memset(st, 0, sizeof st);
        
        sum = 0;
        for(int i=0; i<n; i++) {
   
            scanf("%d", &w[i]);
            sum += w[i];
        }
        
        //搜索剪枝
        sort(w, w+n, cmp);
        
        len = 1;
        while(1) {
   
            if(sum%len==0 && dfs(0, 0, 0)) {
   
                printf("%d\n", len);
                break;
            }
            len++;
        }
        
    }
    
    return 0;
}

168. 生日蛋糕