思路:
转换为多重背包问题,将总价值求出,然后分两半,对于一个人当总花费为总价值的一半时,看得到的价值是否等于总花费;
AC代码:
#include<stdio.h> int a[7]; int dp[120000]; int V; void CompletePack(int c,int w) { int v; for(v=c;v<=V;v++) if(dp[v]<dp[v-c]+w) dp[v]=dp[v-c]+w; } void ZeroOnePack(int c,int w) { int v; for(v=V;v>=c;v--) if(dp[v]<dp[v-c]+w) dp[v]=dp[v-c]+w; } void MultiplePack(int c,int w,int amount) { int k; if(c*amount>V) { CompletePack(c,w); return; } k=1; while(k<amount) { ZeroOnePack(k*c,k*w); amount-=k; k*=2; } ZeroOnePack(amount*c,amount*w); } int main() { int i; int sum; int count=1; while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])!=-1&&(a[1]+a[2]+a[3]+a[4]+a[5]+a[6])!=0) { sum=0; for(i=1;i<=6;i++) { sum+=i*a[i]; } if(sum%2) { printf("Collection #%d:\nCan't be divided.\n\n",count++); continue; } V=sum/2; for(i=0;i<=V;i++)dp[i]=0; for(i=1;i<=6;i++) MultiplePack(i,i,a[i]); if(dp[V]==V) printf("Collection #%d:\nCan be divided.\n\n",count++); else printf("Collection #%d:\nCan't be divided.\n\n",count++); } return 0; }