背包九講–混合背包和分組背包問題
混合背包顧名思義是講0/1，多重和完全背包混合起來的背包問題，我們處理這種背包問題一般是進行條件判斷處理然後在進行三個背包問題分析就可以了。
實戰項目：//www.acwing.com/problem/content/description/7/
//www.luogu.com.cn/problem/P1833；
程式碼以及注意事項如下：
1 //沒有注意事項，前面的問題分析都有，不多重複 2 #include<bits/stdc++.h> 3 using namespace std; 4 int dp[10100]; 5 int n,v; 6 int value,weight,s; 7 int main() 8 { 9 ios::sync_with_stdio(false); 10 cin>>n>>v; 11 for (register int i = 1; i <= n; i++) { 12 cin >>weight>>value>>s; 13 if (s== 0) 14 for (int j = weight; j <= v; j++) 15 dp[j] = max(dp[j], dp[j - weight] + value); 16 else if (s== -1) 17 for (int j = v; j >=weight; j--) 18 dp[j] = max(dp[j], dp[j -weight] +value); 19 else { 20 int num = min(s, v /weight); 21 for (int k = 1; num > 0; k <<= 1) { 22 if (k > num) 23 k = num; 24 num -= k; 25 for (int j = v; j >= weight * k; j--) 26 dp[j] = max(dp[j], dp[j - weight * k] +value* k); 27 } 28 } 29 } 30 cout<<dp[v]<<endl; 31 return 0; 32 }
2.分組背包問題：
有 N組物品和一個容量是 V 的背包。
每組物品有若干個，同一組內的物品最多只能選一個。
每件物品的體積是vij，價值是wij，其中 i是組號，j 是組內編號。
求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價值最大。
輸出最大價值
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選
那我們可以這樣處理：
for (int i = 1; i <= n; i++) { cin >> s; for (int j = 1; j <= s; j++) cin >> c[j] >> w[j]; for (int j = v; j >= 0; j--) for (int k = 1; k <= s; k++) if (j >= c[k]) f[j] = max(f[j], f[j - c[k]] + w[k]); }
需要注意的是，對於三層for循環必須要保證j循壞在k循環的外面才能保證取物品是不衝突的，達到分組背包的目的；
項目實戰：
//www.acwing.com/problem/content/description/9/
//www.luogu.com.cn/problem/P1757#sub
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,v; 4 int f[1010]; 5 int s; 6 int c[1010]; 7 int w[1010]; 8 int main() 9 { 10 ios::sync_with_stdio(false); 11 cin>>n>>v; 12 for (int i = 1; i <= n; i++) { 13 cin >> s; 14 for (int j = 1; j <= s; j++) cin >> c[j] >> w[j]; 15 for (int j = v; j >= 0; j--) 16 for (int k = 1; k <= s; k++) 17 if (j >= c[k]) 18 f[j] = max(f[j], f[j - c[k]] + w[k]); 19 20 } 21 22 cout<<f[v]<<endl; 23 return 0; 24 }
洛谷：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int dp[1010]; 4 int weight[1010]; 5 int value[1010]; 6 int s[1010]; 7 int n,m; 8 int com; 9 int main() 10 { 11 ios::sync_with_stdio(false); 12 cin>>m>>n; 13 for(register int i=1;i<=n;i++) 14 { 15 cin>>weight[i]>>value[i]>>s[i]; 16 com=max(com,s[i]);//確定組數 17 } 18 for(register int i=1;i<=com;i++)//對組進行循環 19 { 20 for(register int j=m;j>=0;j--)//對重量進行循環 21 { 22 for(register int k=1;k<=n;k++)//對物品進行循環 23 { 24 if(s[k]!=i||j<weight[k])//裝不下就跳過 25 continue; 26 else 27 dp[j]=max(dp[j],dp[j-weight[k]]+value[k]);//狀態以及轉移方程 28 } 29 } 30 } 31 cout<<dp[m]<<endl; 32 return 0; 33 }
