企业官网建设流程全解析

题目
有价值分别为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 1
9 8 1 7 2 4
6 6 8 5 9 2
1 6 6 1 0 7
5 9 3 8 8 4
0 0 0 0 0 0
输出样例：
Can’t
Can
Can’t
Can’t
Can
注：本人想借此题来巩固一下多重背包的二进制优化。
算法多重背包+二进制优化
二进制优化的最大看头就是将n个相同的物品分成log(n)个物品。
以下为本题的划分代码

for(int i=1;i<=6;i++){ int k=a[i],c=1; while(1){ if(k<c){ v[++cnt]=i*k; break; } k-=c; v[++cnt]=i*c; c*=2; } }

判定一组大理石能否划分成相等的两部分，
就只需要判定能否从这堆石头里挑出价值和为sum/2的石块

#include<bits/stdc++.h> using namespace std; const int ll=1e6; int a[6]; int f[ll]; int v[1000]; int main(){ while(1){ memset(f,0,sizeof(f)); int sum=0,cnt=0; for(int i=1;i<=6;i++){ cin>>a[i]; sum+=a[i]*i; } if(!sum) break; for(int i=1;i<=6;i++){ int k=a[i],c=1; while(1){ if(k<c){ v[++cnt]=i*k; break; } k-=c; v[++cnt]=i*c; c*=2; } } f[0]=1; for(int i=1;i<=cnt;i++) for(int j=sum;j>=v[i];j--) f[j]|=f[j-v[i]]; if(sum&1) printf("Can't\n"); else{ if(f[sum/2]) printf("Can\n"); else printf("Can't\n"); } } return 0; }