学步园

题意：有n个物品，每个物品有一个val[i]以及一个时间限制t[i],求再最大时间限制为L时，选择M个物品的最大sumval。

这道题背包的第二维隐藏在只能从n个物品种选择M个这个限制，另一个就是总的时间限制L。

我们可以看成每个物品占用一个可选容量和一个时间限制。可选容量恒为1，而时间限制维t[i]。

状态转移方程dp[k][i][j]=Max(dp[k-1][i-1][j-t[k]]+val[k],dp[k-1][i][j])

有几个陷阱要注意

此题中对第一维的要求是必须选择M个物品，第二维的要求时，只要时间小于L都可以。

因此我们初始化dp，  memset(dp,0x80,sizeof(dp))，是一个非常小的负数。

在背包问题中有如下规定：

如果是要求背包恰好装满的最大值，那么初始化除了dp[0][0]=0,其他都为-inf 
如果没必要把背包装满，而只要求价值最大，那么直接初始化为0就可以了。

解的“连续性”决定了这个规则。

由于第二维不需要装满，因此只要在dp[M][j]中选择最大的那个即可。如果第二维必须装满，则只能选择dp[M][L]

#include<iostream>
#include<cstring>
#define Max(a,b) (a<b?b:a)
#define Min(a,b) (a<b?a:b)
using namespace std;

int c_count;
int N,M,L;  
int t[101];
int val[101];
/*二维背包，设dp[k][i][j]为只使用前k种物品，选择其中i种物品，花费为j时的最大收益。*/
/*物品总个数限制and最大花费限制*/
/*且最后求的是背包第一维恰好满时的最大值*/
/*转移方程 dp[k][i][j]=Max(dp[k][i][j],dp[k-1][i-1][j-t[m]]+val[m])*/
int dp[101][1001];


int main(){
	cin>>c_count;
	while(c_count--){
		cin>>N>>M>>L;
		for(int i=0;i<N;i++){
			cin>>t[i]>>val[i];
		}
		memset(dp,0x80,sizeof(dp));
		dp[0][0]=0;
		for(int i=0;i<N;i++){
			for(int j=M;j>=1;j--){
				for(int k=L;k>=t[i];k--){
					dp[j][k]=Max(dp[j-1][k-t[i]]+val[i],dp[j][k]);
				}
			}
		}
		int ans=0;
		for(int i=L;i>=0;i--){
			if(dp[M][i]>ans){
				ans=dp[M][i];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}