318. 划分大理石

题目有价值分别为1…6的大理石各a[1…6]块现要将它们分成两部分使得两部分价值之和相等问是否可以实现。其中大理石的总数不超过20000。输入格式输入包含多组数据每组数据占一行包含6个整数表示a[1]~a[6]。当输入为0 0 0 0 0 0时表示输入结束且该行无需考虑。输出格式每组数据输出一个结果每个结果占一行。如果可以实现则输出“Can”否则输出“Can’t”输入样例4 7 4 5 9 19 8 1 7 2 46 6 8 5 9 21 6 6 1 0 75 9 3 8 8 40 0 0 0 0 0输出样例Can’tCanCan’tCan’tCan注本人想借此题来巩固一下多重背包的二进制优化。算法多重背包二进制优化二进制优化的最大看头就是将n个相同的物品分成log(n)个物品。以下为本题的划分代码for(int i1;i6;i){ int ka[i],c1; while(1){ if(kc){ v[cnt]i*k; break; } k-c; v[cnt]i*c; c*2; } }判定一组大理石能否划分成相等的两部分就只需要判定能否从这堆石头里挑出价值和为sum/2的石块#includebits/stdc.h using namespace std; const int ll1e6; int a[6]; int f[ll]; int v[1000]; int main(){ while(1){ memset(f,0,sizeof(f)); int sum0,cnt0; for(int i1;i6;i){ cina[i]; suma[i]*i; } if(!sum) break; for(int i1;i6;i){ int ka[i],c1; while(1){ if(kc){ v[cnt]i*k; break; } k-c; v[cnt]i*c; c*2; } } f[0]1; for(int i1;icnt;i) for(int jsum;jv[i];j--) f[j]|f[j-v[i]]; if(sum1) printf(Cant\n); else{ if(f[sum/2]) printf(Can\n); else printf(Cant\n); } } return 0; }