hdu 1059 练习练习dp(多重背包)

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int size = 600000;
int sum;
int dp[size];
void zeroOnePack(int cost,int weight)
{
	int i;
	for(i=sum;i>=cost;i--)
		dp[i] = max(dp[i],dp[i-cost]+weight);
}
void completePack(int cost,int weight)
{
	int i;
	for(i=cost;i<=sum;i++)
		dp[i]=max(dp[i],dp[i-cost]+weight);
}
void MultiPack(int cost,int weight,int count)
{
	int i=1;
	if(cost*count>=sum)
	{
		completePack(cost,weight);
		return ;
	}
	while(i<count)
	{
		zeroOnePack(cost*i,weight*i);
		count-=i;
		i<<=1;
	}
	zeroOnePack(cost*count,weight*count);
}
int main()
{
	int num[7],no=1,i;
	while(1)
	{
		sum = 0;
		for(int i=1;i<7;i++)
		{
			cin>>num[i];
			sum+=num[i]*i;
		}
		if(!sum)
			break;
		if(sum&1)
			cout<<"Collection #"<<no++<<":"<<endl<<"Can't be divided."<<endl<<endl;
		else
		{
			sum>>=1;
			for(i=0;i<=sum;i++)
				dp[i] = 0;
			for(i=1;i<7;i++)
				if(num[i])
					MultiPack(i,i,num[i]);
			if(dp[sum]==sum)
				cout<<"Collection #"<<no++<<":"<<endl<<"Can be divided."<<endl<<endl;
			else
				cout<<"Collection #"<<no++<<":"<<endl<<"Can't be divided."<<endl<<endl;
		}
	}
	return 0;
}

补充：软件开发 , C++ ,

上一个：图的着色问题 （也就是最少着色问题，时间复杂度为N^2)
下一个：C，C++中的static