#include<stdio.h>int dp[120005];int V,v;void bag01(int c,int w)//01背包{ for(v=V; v>=c; v--) if(dp[v]<dp[v-c]+w) dp[v]=dp[v-c]+w;}void bagall(int c,int w)//完全背包{ for(v=c; v<=V; v++) if(dp[v]<dp[v-c]+w) dp[v]=dp[v-c]+w;}void mutibag(int c,int w,int p)//多重背包{ if(c*p>=V) bagall(c,w); else { int k=1; while(k<p) { bag01(c*k,w*k); p=p-k; k=k+k; } bag01(c*p,w*p); }}int main(){ int n[8]; int i,sum,p=0; while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]),n[1]+n[2]+n[3]+n[4]+n[5]+n[6]) { sum=n[1]+n[2]*2+n[3]*3+n[4]*4+n[5]*5+n[6]*6; //sum为奇数个，那么肯定不能平分 if(sum%2) { printf("Collection #%d:\nCan't be divided.\n\n",++p); continue; } V=sum/2; for(i=0; i<=V; i++) dp[i]=0; for(i=1; i<=6; i++) mutibag(i,i,n[i]); if(dp[V]==V) printf("Collection #%d:\nCan be divided.\n\n",++p); else printf("Collection #%d:\nCan't be divided.\n\n",++p); } return 0;}
转载于:https://www.cnblogs.com/Skyxj/p/3196942.html
