changed 3 years ago  
Published Linked with GitHub

剪枝

題目:給n件物品，每件重量不同，可分給任意個人(>=2)，但是每個人的重量要一樣，求平分後的最小重量

分析:

  1. 假設能平分的最小重量為w，則sum必是w的倍數
    sum % w == 0
  2. w不能小於最大的元素，因為這樣就放不下了
    i >= max_element(W[i])
  3. w不可超過sum/2，因為這樣就只會被分成一堆
    w <= sum/2
  4. 為了節省速度，有大的就先取大的，大的不夠再拿小的來補
    sort(all(w),vector<>())

依據上面的推斷，可以在這些範圍內枚舉











sort(all(w),greater<>());

for(int i=w[0];i<=sum/2;i++){
    if(sum%i) continue;
    
    if(dfs(...)){
        cout << i << '\n';
        break;
    }
}

接著進今天的主題:剪枝

在枚舉的時候有以下幾點可以直接略過，以加快dfs的速度

  1. 不用把各堆物品的數量記起來，一次只配一個，配完再換下一個
  2. 每次尋找新的堆時，先用最大的，再去尋找能與它配對成maxW的其他重量
  3. 如果當前重量已經匹配過的話就不能再給別人了
  4. 如果當前重量和前一個相同時，前一個沒有選代表了不是一個合法的解，選當前重量也就沒意義
  5. 如果當前重量加上w_i會超重的話，不合法
  6. 最後檢查如果剩餘重量等於當前遍歷到的重量時，就直接return false，因為此時是最佳解，不合法的話代表後面也不會有合法的答案
  7. 如果完成匹配，所有遞迴都直接return



























int used[MAXN],w[MAXN],total,maxW;

bool dfs(int W,int complete,int now){  
    //(1) W為當前配了多重,complete為配完幾組,now為現在遍歷的節點編號
    
    if(W==maxW){  //匹配完一組的時候
        complete++;  //完成的配對數+1
        if(complete==total) return true;  //(7) 完成匹配
        else{
            for(now=0;used[now];now++);  //(2) 先用最大的
            used[now]=true;
            if(dfs(w[now],complete,now+1)) return true;  //找到解直接回傳
            used[now]=false;
        }
    }else{
        for(int i=now;i<n;i++){  //遍歷每個節點
            if(used[i] || (i && !used[i-1] && w[i-1]==w[i]) || W+w[i]>maxW) continue;  //(3) (4) (5) 避免不必要的遞迴
            used[i]=true;
            if(dfs(W+w[i],complete,i+1)) return true;  //找到解直接回傳
            used[i]=false;
            
            if(W+w[i]==maxW) return false;  //(6)
        }
    }
    return false;
}

for迴圈要更新maxW及total:










for(int i=w[0];i<=sum/2;i++){
    if(sum%i) continue;
    
    maxW=i,total=sum/i;
    if(dfs(0,0,0)){
        cout << i << '\n';
        return;
    }
}

d785: 二、正邊形



























































#include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define MAXN 100
using namespace std;

int a[MAXN],maxW,n,m,N;
bool used[MAXN];

bool dfs(int w,int cnt,int now){
    if(w==maxW){
        cnt++;
        if(cnt==m) return true;
        else{
            for(now=0;used[now];now++);
            
            used[now]=true;
            if(dfs(a[now],cnt,now+1)) return true;
            used[now]=false;
        }
    }else{
        for(int i=now;i<n;i++){
            if(used[i] || (a && a[i-1]==a[i] && !used[i-1]) || w+a[i]>maxW) continue;
            
            used[i]=true;
            if(dfs(w+a[i],cnt,i+1)) return true;
            used[i]=false;

            if(w+a[i]==maxW) return false;
        }
    }
    return false;
}

int main(){
    cin.sync_with_stdio(0),cin.tie(0);
    
    cin >> N;
    while(N--){
         cin >> m >> n;
        mem(used);
        
        int sum=0;
        for(int i=0;i<n;i++){
            cin >> a[i];
            sum+=a[i];
        }
        sort(a,a+n,greater<int>());
        if(sum%m){
            cout << 0 << '\n';
            continue;
        }

        maxW=sum/m;
        if(dfs(0,0,0)) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}
Select a repo