hdu 3496 二维费用背包

点击打开链接

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int inf=1<<30;
const int M =1100;			// 时间->体积  评分 ->价值 
int dp[M][M]; 	//  dp[i][j][k] 前I件选不超过J件装进体积为K的最大val 
					// 决策 第i件选或者不选
					// 	dp[i][j][k]= max(dp[i-1][j][k],dp[i-1][j-1][k-T[i]]+val[i]); 
int time[M],val[M];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,T;
		cin>>n>>m>>T;
		for(int i=1;i<=n;i++)
		{
			cin>>time[i]>>val[i];
		}
		
		// the shop just sell M piece of movies (not less or more then 件数要满 
		for(int j=0;j<=m;j++) //前0件选j时间k 
		{
			for(int k=0;k<=T;k++)
			{
				if(j==0)
				{
					dp[j][k]=0;
				}
				else
				{
					dp[j][k]=-inf; //	一定要装满 装不满设为负  
				}
			}
		}
		  
		
		for(int i=1;i<=n;i++) //优化到二维  dp[j][k] 前i件 选j件 体积不超过k的最大val 
		{						 
			for(int j=m;j>=1;j--) //逆推: 保证求dp[j][k]时  dp[j][k]和dp[j-1][k-time[i]] 都是来自 前i-1件的 
			{
				for(int k=T;k>=0;k--) 
				{
					if(k>=time[i]) //是否能选第i件 
					dp[j][k]=max(dp[j][k],dp[j-1][k-time[i]]+val[i]);		 
				}
			}
		}
		if(dp[m][T]<0)
		cout<<0;
		else
		cout<<dp[m][T];
		cout<<endl;
	}
	return 0;
}