学步园

HDOJ 2191 题目描述

下面用的是最基本的多重背包转01背包方法做的，没有用单调队列优化，因为还没研究。

/*
HDOJ 2191
多重背包问题，下面是用最基本的转化方法
将其转化为01背包问题，未优化的
*/

#include <iostream>
using namespace std;

int main()
{
	int nCase,Limit,nKind,i,j,k,
		price[101],weight[101],bag[101],dp[101];
	
	cin>>nCase;
	while(nCase--)
	{
		cin>>Limit>>nKind;
		for(i=0;i<nKind;i++)
			cin>>price[i]>>weight[i]>>bag[i];

		memset(dp,0,sizeof(dp));

		for(i=0;i<nKind;i++)
			for(j=0;j<bag[i];j++)
				for(k=Limit;k>=price[i];k--)
					if(dp[k] < dp[k-price[i]]+weight[i])
						dp[k]=dp[k-price[i]]+weight[i];

		cout<<dp[Limit]<<endl;
	}
	return 0;
}