題目
連結
大意：有一個容量為$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\n", 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
個性簽名：時間會解決一切