View Code of Problem 150

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<map>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2000000;
int dp[maxn];
int volume[maxn], value[maxn], c[maxn];
int n, v; // 总物品数，背包容量量
//val 最大容量,val 总价值,amount 数量
// 01 背包
void ZeroOnepark(int val, int vol) {
	for (int j = v ; j >= vol; j--)
		dp[j] = max(dp[j], dp[j - vol] + val);
}
//完全背包
void Completepark(int val, int vol) {
	for (int j = vol; j <= v; j++)
		dp[j] = max(dp[j], dp[j - vol] + val);
}

// 多重背包 
void Multiplepark(int val, int vol, int amount) {
	int k = 1;
	while (k < amount) {
		ZeroOnepark(k * val, k * vol);
		amount -= k;
		k <<= 1;
	}
	if (amount > 0)
		ZeroOnepark(amount * val, amount * vol);
}
int m;
int main(){
	int count=1;
	while(1){
		memset(dp,0,sizeof(dp));
		int sum=0,flag=1;
		for(int i=1;i<=6;i++)
        {
            scanf("%d",&c[i]);
            if(c[i])
            	flag=0;
            sum+=c[i]*i;
        }

        if(flag)
        	break;
        
		if((sum%2)!=0){
			printf("Collection #%d:\nCan't be divided.\n\n",count++);//吐了，这里一直写成can be，一直wa
		}
		else{
			v=sum/2;

			for(int i=1;i<=6;i++){
				Multiplepark(i,i,c[i]);
			}
//			cout<<dp[v]<<endl;
			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;
}