알고리즘 과 데이터 구조 - 가방 문제

/**
 *       ：    i   (i  )    
 * cost：i      c[i]
 * weight：i      v[i]
 * amount：i          n[i]
 * CompletePack：      
 * ZeroOnePack：01    
 */
void MultiplePack(cost,weight,amount){
	if(cost*amount>=capacity){
		CompletePack(cost,weight);return;
	}
	int k=1;
	while(k<amount){ 
		ZeroOnePack(k*cost,k*weight);
		amount=amount-k;
		k=k*2;
	}
	ZeroOnePack(amount*cost,amount*weight);
}

：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=149

：

1、2、3、4、5、6 6 （ ⊙﹏⊙b ）， ， ， ， 。

：

， cost ， 。

：

#include <iostream>
#define MAX 210002
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
long nums[6],total,f[MAX];

int input(){
	for(int i=total=0;i<6;i++){
		cin>>nums[i];
		total+=nums[i]*(i+1);
	}
	if(total)return 1;
	return 0;
}

void zeroOnePack(int cost,int value,long capacity){
	for(int j=capacity;j>-1;j--)
		if(j>=cost)f[j]=max(f[j],f[j-cost]+value);
}
void completePack(int cost,int value,long capacity){
	for(int j=0;j<=capacity;j++)
		if(j>=cost)f[j]=max(f[j],f[j-cost]+value);
}
void multiplePack(int cost,int value,int count,long capacity){
	if(cost*count>=capacity){
		completePack(cost,value,capacity);
		return;
	}
	int k=1;
	while(k<count){
		zeroOnePack(cost*k,value*k,capacity);
		count-=k;
		k*=2;
	}
	zeroOnePack(cost*count,value*count,capacity);
}

int judge(long capacity){
	for(int i=0;i<6;i++){
		if(i==0){
			for(int j=0;j<=capacity;j++)
				if(j<i+1)f[j]=0;
				else{
					int amount=j/(i+1);
					f[j]=(nums[i]>=amount ? (i+1)*amount : nums[i]*(i+1));
				}
		}
		else multiplePack(i+1,i+1,nums[i],capacity);
	}
	if(f[capacity]==capacity)return 1;
	return 0;
}

int main()
{
	int T=1;
	while(input()){
		printf("Collection #%d:
",T++);
		if(total&1)cout<<"Can't be divided."<<endl<<endl;
		else if(judge(total/2))cout<<"Can be divided."<<endl<<endl;
		else cout<<"Can't be divided."<<endl<<endl;
	}
	return 0;
}