題目傳送門
一、思路分析
(1)狀态表示\(f[i][j]\)
集合:隻從前\(i\)組物品中選,且總體積不大于\(j\)的所有選法
屬性:\(Max\)
(2) 狀态計算[集合劃分的思考過程]
完全背包問題是枚舉第\(i\)個物品選幾個(或者0個),分組背包問題枚舉第\(i\)組物品選哪個(或者不選),有點拗口啊。
二、二維數組版本
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N][N];
//分組背包
int main() {
//優化輸入
ios::sync_with_stdio(false);
cin >> n >> m; //物品組數,背包容量
for (int i = 1; i <= n; i++) {
//第i組中的物品數量
cin >> s[i];
for (int j = 1; j <= s[i]; j++)
cin >> v[i][j] >> w[i][j]; //讀入每組物品的體積,價值
}
for (int i = 1; i <= n; i++) //前i組物品
for (int j = 0; j <= m; j++) //背包容量從小到大
for (int k = 1; k <= s[i]; k++) {//周遊第k個物品
f[i][j] = max(f[i - 1][j], f[i][j]);
if (j >= v[i][k])
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
cout << f[n][m] << endl;
return 0;
}
三、一維數組版本
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n; //n類物品
int m; //背包上限為m
int v[N][N]; //價值
int w[N][N]; //體積
int s[N]; //個數
int f[N]; //dp數組,最大值
//分組背包
int main() {
//優化輸入
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {//枚舉每類物品,比如:水果,蔬菜,肉類...
cin >> s[i]; //此類物品中物品的個數,比如2,可能是蘋果、香蕉
for (int j = 1; j <= s[i]; j++)//讀入蘋果、香蕉的價值和體積
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i++) //周遊每類物品
for (int j = m; j >= 0; j--) //周遊每個可能的體積
for (int k = 1; k <= s[i]; k++)//周遊第k個物品
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}