[数据结构与算法]1163. 易于执行的 DP (DFS)

1163. 易于执行的 DP

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000;
vector<int> weight;
vector<bool>visit;
int diff,n,W;           //最小差值，饼干总数, 饼干总重量
void dfs(int index,int wTemp){     //wTemp为此时一方的饼干重量
    diff=min(diff,abs(W-2*wTemp));
    if(2*wTemp>W) return;
    for(int i=index;i<n;++i){
        if(visit[i]==false) {
            visit[i]=true;
            dfs(i,wTemp+weight[i]);
            visit[i]=false;
        }
    }
    return;
}
int main() {
    while(scanf("%d",&n)!=EOF){
        weight.resize(n),visit.resize(n);
        W=0,diff=MAXN;
        for(int i=0;i<n;++i){
            scanf("%d",&weight[i]);
            W+=weight[i]; 
        }
        fill(visit.begin(),visit.end(),false);
        dfs(0,0);
        printf("%d\n",diff);
    }
    system("pause");
    return 0;
}