Partition marble (multiple knapsack + binary optimization)

Divide the marble （ Multiple backpack + Binary optimization ）

Description
The values are 1…6 Of marble a[1…6] block , Now I want to divide them into two parts , Make the sum of the two parts equal , Ask if you can achieve . The total number of marble is not more than 20000.

Input
There are multiple sets of data ！
So how could it be
If there is 0 0 0 0 0 0 Indicates the end of the input file
The rest of the action 6 It's an integer

Output
How many lines of feasible data are output
If the division succeeds , Output Can, otherwise Can’t

Samples
Input Copy
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

Output
Can’t
Can
Can’t
Can’t
Can

Ideas ： This problem is multiple backpacks . Ask if it can be divided into two equal parts , It can be transformed into sum/2 Whether there is , If there is , Then the rest must be equal to sum/2;

General multiple backpacks ：（ Simple algorithm ）

	//n Items , Capacity of m The backpack , Each item has a maximum of s[i] individual , The volume is v[i], Value is w[i], ask 
	// Package maximum value  
	for(int i=1;i<=n;i++){
    
		for(int j=m;j>=v[i];j--){
    
			for(int k=0;k*v[i]<=j&&k<=s[i];k++){
    
				f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
			}
		}
	}

Binary optimization

//n Items , Capacity of m The backpack , Each item has a maximum of s[i] individual , The volume is v[i], Value is w[i], ask 
// Package maximum value  
// hypothesis  50 An apple , take n individual , If the naive algorithm is one by one , But binary is to 50 An apple is divided into several parts （1,2,4,8,16,29( Because the rest is not satisfied 2*16） Add these ==50） These can be made up of anything 50 Any number within , hypothesis n yes 6, The naive algorithm should 6 Time , Binary must 2 Time （2,4）
	int vv[maxn],ww[maxn],tot=0;
	for(int i=1;i<=n;i++){
    
		for(int j=1;j<=s[i];j*=2){
    
			vv[++tot]=v[i]*j;
			ww[tot]=w[i]*j;
			s[i]-=j;
		}
		if(s[i]){
    
			vv[++tot]=v[i]*s[i];
			ww[tot]=w[i]*s[i];
		}
	} 
	for(int i=1;i<=tot;i++){
    
		for(int j=m;j>=vv[i];j--){
    
			f[j]=max(f[j],f[j-vv[i]]+w[i]);
		}
	}

AC Code ：

int a[7];
int w[maxn];
int f[maxn];
int main(){
    
	while(1){
    
		int sum=0,aa=0;
		int num=0;
		for(int i=1;i<=6;i++) {
    
			cin>>a[i],sum+=i*a[i];
			if(!a[i]) aa++;
			for(int j=1;j<=a[i];j*=2){
    
				w[++num]=i*j;
				a[i]-=j;
			}
		if(a[i]) w[++num]=a[i]*i;
		}
		if(aa==6) return 0;
		if(sum&1) {
    
			puts("Can't");
			continue;
		}
		memset(f,0,sizeof(f));
		f[0]=1;
		for(int i=1;i<=num;i++){
    
			for(int j=sum/2;j>=w[i];j--){
    // Here the volume is replaced by the value , Whether there is ！！！ miao 
				f[j]=max(f[j],f[j]+f[j-w[i]]);
			}
		}
		if(f[sum/2]) cout<<"Can\n";
		else puts("Can't");
	}
	return 0;
}