/* ID: LANG: PROG: */ #include #include #include #include int num[6]; int used[6*20000]; short can[6*20000]; /*O(NV)的复杂度的多重背包*/ int work(int total) { int i,j,k; memset(can,0,sizeof(can)); memset(used,0,sizeof(used)); can[0] = 1; for(i = 0;i < 6;i++) {/*外循环枚举每一种物品*/ memset(used,0,sizeof(used));/*这种物品还没用过一件*/ for(j = 0;j <= total;j++) {/*枚举可能的值*/ if(0 == can[j])/*如果这个值没算过*/ { k = j - (i+1);/*是否可以通过加一个价值为(i+1)的物品得到总价值为j的*/ if(k >= 0 && can[k])/*k>=0而且价值为k的可以到达 */ { used[j] = used[k]+1;/*比总价值为k的多用一个价值为(i+1)的物品*/ if(used[j] <= num[i])/*如果价值为(i+1)的物品还有剩的话*/ {/*也就是说总价值为j的物品可以通过总价值为k的加上一个价值*/ /*为(i+1)的物品得到*/ can[j] = 1; } } } } } if(can[total/2])/*如果所有硬币的总价值的一半可以通过某些硬币得到的话*/ return 1; return 0; } int main(void) { int i; int idx=0; int flag,sum; while(1) { flag = 1; sum = 0; for(i = 0;i < 6;i++) { scanf("%d",&num[i]); if(num[i])/*有一个num[i]不为0就置flag为0*/ flag = 0; sum += (i+1)*num[i];/*所有石子的总价值*/ } if(flag)/*flag为1就跳出循环*/ break; idx++; if(sum&1)/*如果总价值是奇数肯定不能划分*/ flag = 0; else flag = work(sum);/*work函数得到能否divided*/ if(flag) printf("Collection #%d:\nCan be divided.\n\n",idx); else printf("Collection #%d:\nCan't be divided.\n\n",idx); } return 0; }