2022 ICPC 杭州 C. No Bug No Game codeforces gym104090C

2022 ICPC 杭州 C. No Bug No Game codeforces gym104090C

Problem - C - Codeforces

题目大意：有n个物品，背包容量为k，每个物品重量为pi，取的重量不同，获得的价值也不同，从1到pi分别为wj,如果当前背包容量足够，则必须取完整的重量，否则才可以取部分重量来填满剩余的背包容量，问能取得的最大价值是多少

1<=n<=3000;0<=k<=3000;1<=pi<=10;1<=wj<=1e5

思路：因为我们对于每个物品只能取当前背包容许的最大重量，所以最多只有一个物品可以取部分重量，这样的问题就是一个多重背包问题，我们既要考虑取哪个物品，又要考虑每个物品怎么取，所以我们开一个三维的数组dp[i][j][jj]，表示当前前i个物品取的总重量为j，有jj个物品取了部分重量，我们先初始化dp[0][0][0]=0，然后用类似01背包的办法，令j从k-1到0遍历，这里的j是取当前第i个物品之前的总重，所以从k开始是无意义的，然后我们首先将dp[i-1][j]的数据转移到dp[i][j]作为之后比较的基值，然后在背包能装下完整物品时，分取和不取两种情况转移，dp[i][j+p]=max(dp[i][j+p],dp[i-1][j]+w[p]),然后我们枚举当前物品的每份重量，dp[i][j+jj][1]=max(dp[i][j+jj][1],dp[i-1][j][0]+w[jj])这样就完成了对取每个物品以及每个物品取多重的枚举，之后遍历i遍历j寻找答案

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
int dp[3005][3005][15];
int w[15];
int main()
{cin.tie(0);ios::sync_with_stdio(false);int n, k;memset(dp, -0x3f, sizeof dp);//将所有数据设成无效值dp[0][0][0] = 0;//初始化取0个物品0重量，没有取部分的物品时的值为0cin >> n >> k;for (int i = 1; i <= n; i++){int p;cin >> p;for (int j = 1; j <= p; j++){cin >> w[j];//每个物品取不同重量的价值}for (int j = k - 1; j >= 0; j--){//取第i个物品前当前取的重量dp[i][j][1] = dp[i - 1][j][1];dp[i][j][0] = dp[i - 1][j][0];//先从上一个物品转移过来用来做之后的比较if (j + p <= k){//当前背包能完整的装下当前物品dp[i][j + p][0] = max(dp[i][j + p][0], dp[i - 1][j][0] + w[p]);dp[i][j + p][1] = max(dp[i][j + p][1], dp[i - 1][j][1] + w[p]);//从i-1,j转移}for (int jj = 1; jj < p && j + jj <= k; jj++){//当前物品取jj份重量dp[i][j + jj][1] = max(dp[i][j + jj][1], dp[i - 1][j][0] + w[jj]);//从i-1,j,0,转移}			}}int ans = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= k; j++){//枚举i，j找到最大值ans = max(ans, dp[i][j][0]);}ans = max(ans, dp[i][k][1]);//对于每个物品，如果要取部分重量，那此时重量肯定的等于背包总重}cout << ans;return 0;
}