#include <iostream> #include <algorithm> using namespace std; int sum = 0; const int inf=99999999; int a[2000]; int mini = inf; void dfs(int x,int n,int step) { if(step > n) //最多拿起n个瓜 return ; int t = 2*x - sum; if(t<0) t = -t; if(t <mini) mini = t; //比如13 1 1,先记录最小差值,先比较13和15/2,发现大于,继续搜索只会让差值2*x-sum值增大 if(x > sum/2) //若先比较后记录,比如5 7 6,只能探测到5,此时记录的差值为8,不合理 return ; //如果拿起的重量已经超过总量的一半,继续拿起只会让差值增大,故剪枝 dfs(x+a[step],n,step+1); dfs(x,n,step+1); } int main() { int n; while(cin >> n) { sum = 0; mini= inf; for(int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } if(n==1) mini = a[0]; else dfs(a[0],n,1); cout << mini << endl; } system("pause"); return 0; }
最优:
#include <stdio.h> #define max(a,b) a>b?a:b int V,ans,n,w[21],sum[21]; void dfs(int i,int cnt) { if(i == 0) { ans = max(ans,cnt); return ; } if(ans == V || cnt+sum[i] <= ans) //cut return ; if(cnt+w[i] <= V) dfs(i-1,cnt+w[i]); dfs(i-1,cnt); } int main() { while(~scanf("%d",&n)) { ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&w[i]); sum[i] = sum[i-1] + w[i]; } V = sum[n]/2; dfs(n,0); printf("%d\n",sum[n]-2*ans); } return 0; }
转载于:https://www.cnblogs.com/ekinzhang/p/4414448.html
相关资源:JAVA上百实例源码以及开源项目