有限制的背包（No Bug No Game）

2022 ICPC杭州 C. No Bug No Game

题目

有n个物品，背包容量为k，给出n组物品，每一组物品有pi个，每个物品的体积从1到pi递增，取的体积不同，获得的价值也不同，体积从1到pi(连续），价值从w1到wj （j=pi）

如果当前背包容量足够，则必须取完整的重量

否则必须可以取部分体积来填满剩余的背包容量，问能取得的最大价值是多少

数据范围：n，k<=3000, pi<=10 , wj<=1e5

思路

1. 对于每一组物品，如果此时剩余容量大于pi，则必须取最后一个，否则必须取相应体积的物品，此时容量为0
2. 而且，体积小的物体可能有更大的价值
3. 显然，取的顺序有所谓，前面组必须取最后，最后一组必须取中间的某个
4. 我们无法贪心的排序，但是可以这样想，只有一组取中间，其他组取最后，可以dp
5. 设dp[i][j][0\1]表示前i组，且此时恰好装了j体积的最大价值，0和1表示，恰好装到j时，前i组有没有取到中间的某个物品

我们发现，这样设转移方程是可以转移的，因为可以表示所有状态，第i组刚结束，并且恰好取到了j，还知道此时是否可以取中间

转移方程见代码

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+10;

ll dp[N][N][2];
ll w[N][15];
ll p[N];
ll n,k;
ll ans=0;
int main() {
	cin>>n>>k;
	ll sum0=0,sum1=0;
	for(int i=1; i<=n; i++) {
		cin>>p[i];
		sum0+=p[i];
		for(int j=1; j<=p[i]; j++) {
			cin>>w[i][j]; 
		}
		sum1+=w[i][p[i]];
	}
	
	if(sum0<=k){
		cout<<sum1<<endl;
		return 0;
	}
	
	//初始化
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=k; j++) {
			dp[i][j][0]=dp[i][j][1]=-1e18;
		}
	}

	dp[0][0][0]=0;//前0个物品,恰好选0体积，而且没有选中间某个物品,最大价值为0

	for(int i=1; i<=n; i++) {
		for(int j=0; j<=k; j++) {
			//可以选择不选当前组
			dp[i][j][0]=dp[i-1][j][0];
			dp[i][j][1]=dp[i-1][j][1];


			//选当前组最后一个物品
			//更新dp[i][j][0],dp[i][j][1]
			if(j>=p[i]) {
				dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-p[i]][0]+w[i][p[i]]);
				dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-p[i]][1]+w[i][p[i]]);
			}
			
			//选当前组的中间物品
			//更新dp[i][j][1]
			for(int t=1; t<p[i]; t++) {
				if(j>=t) {
					dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-t][0]+w[i][t]);
				}
			}
			
			
			/*
				千万不可以这样写！！！ 
				ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
			*/
		}
	}
	
	//cout<<ans<<endl; 
	cout<<max(0ll,max(dp[n][k][0],dp[n][k][1]));
	return 0;
}

易错点

/*
				千万不可以这样写！！！ 
				ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
*/

• 为什么不可以这样做？？

设想这样一个情景，假设有一组，其中物品价值是 1， 1，INF，1，1

此时，dp[i][j][1]可以是前i组，容量恰好选完j，且此时选到了中间的INF，此时价值是正无穷，可是，如果实际情况是永远也不可能选到INF，这样更新会导致答案错误。

下面证明实际情况存在可能选不到INF：

1. 前i-1层遍历完，并且仅dp[i-1][j][0]有值，dp[i-1][[j][1]为-INF，实际上，不需要考虑dp[i-1][j][1]
2. 遍历第i层，dp[i][j][1]用dp[i-1][j’][0]更新，此时遇到了INF,被更新为INF，导致答案错误