题目
大意：有一个容量为$c$的背包，有$n$个$s_1$类物体，价值都为$k_1$，体积分别为$s_{1,1}, s_{1,2}, cdots, s_{1,n}$，有$m$个$s_2$类物体，价值都为$k_2$体积分别为$s_{2,1}, s_{2,2}, cdots, s_{2,m}$，求背包能装下的最大价值。（价值的计算方法：$k_i * (c - s_i)$）
分析
背包问题，但又要 先做贪心的处理，为什么可以贪心呢？因为有这样一个事实，对于同一类物品，肯定是优先放体积小的，因为体积小r就大，因此先对两类物品按照体积分别排序。
所以最终选的物品的结果肯定是第一类物品的前i项，第二类物品的前j项 $（i,j >= 0）$
所以我们可以很轻松地定义DP中的“状态”了。定义$dp[i][j]$为取了第一类物品的前$i$项，第二类物品的前$j$项 所获得的价值。
状态转移方程 ：
$dp[i][j] = max { dp[i-1][j] + (C - Sum1[i] - Sum2[j] )*k1, dp[i][j-1] + (C - Sum2[j] - Sum1[i] )*k1 }$
其中$Sum1 $是第一类物品体积前缀和，$Sum2$ 是第二类物品体积前缀和。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 const int maxn = 2000 + 10; 6 const int maxm = 2000 + 10; 7 int k1, k2, cap, n, m; 8 int s1[maxn], s2[maxm]; 9 ll sum1[maxn], sum2[maxm], dp[maxn][maxm]; 10 11 int main() 12 { 13 int T; 14 scanf("%d", &T); 15 while(T--) 16 { 17 scanf("%d%d%d", &k1, &k2, &cap); 18 scanf("%d%d", &n, &m); 19 for(int i = 1;i <= n;i++) scanf("%d", &s1[i]); 20 for(int i = 1;i <= m;i++) scanf("%d", &s2[i]); 21 sort(s1+1, s1+n+1); 22 sort(s2+1, s2+m+1); 23 for(int i = 1;i <= n;i++) sum1[i] = sum1[i-1] + s1[i]; //可以看作只从一者取，也可看做初始化边界 24 for(int i = 1;i <= m;i++) sum2[i] = sum2[i-1] + s2[i]; // 25 26 ll ans = -1; 27 for(int i=1; i <= n;i++) 28 { 29 if(cap < sum1[i]) break; 30 dp[i][0] = dp[i-1][0] + (cap - sum1[i]) * k1; 31 ans = max(ans, dp[i][0]); 32 } 33 for(int i=1; i <= m;i++) 34 { 35 if(cap < sum2[i]) break; 36 dp[0][i] = dp[0][i-1] + (cap - sum2[i]) * k2; 37 ans = max(ans, dp[0][i]); 38 } 39 40 for(int i = 1;i <= n;i++) 41 for(int j = 1;j <= m;j++) 42 { 43 if(cap < sum1[i]+sum2[j]) break; 44 dp[i][j] = max(dp[i-1][j] + k1 * (cap - sum1[i] - sum2[j]), dp[i][j-1] + k2 * (cap - sum1[i] - sum2[j])); 45 ans = max(ans, dp[i][j]); 46 } 47 printf("%lld ", ans); 48 } 49 return 0; 50 }
参考链接：
1. 分析 https://www.cnblogs.com/czsharecode/p/9606768.html
2. 代码 https://blog.csdn.net/qq_41156122/article/details/79855315