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) {
	if (vol * amount >= v)
		Completepark(val, vol);
	else {
 		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){
		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;
        v=sum/2;
        v=v/2;
		memset(dp,0,sizeof(dp));

		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",count++);
    	else
    		printf("Collection #%d:\nCan't be divided.\n",count++);
	}
	
	return 0;
}