题目描述
有 $N$ 组物品和一个容量是 $V$ 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$,价值是 $w_{ij}$,其中 $i$ 是组号,$j$ 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 $N$,$V$,用空格隔开,分别表示物品组数和背包容量。
接下来有 $N$ 组数据:
每组数据第一行有一个整数 $S_i$,表示第 $i$ 个物品组的物品数量;
每组数据接下来有 $S_i$ 行,每行有两个整数 $v_{ij}$,$w_{ij}$,用空格隔开,分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值;
输出格式
输出一个整数,表示最大价值。
数据范围
$0<N,V≤100$,
$0<Si≤100$,
$0<v_{ij},w_{ij}≤100$,
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例:
8
思路
状态可以用f[i][j][k]
,表示选到第i
个组,体积小于等于j
,选择第i
组里的第k
个物品。
由此f[i][j][k]
可以这么算:
1. 不在当前这组选, 即f[i-1][j][s[i-1]]
。
2. 选第i
组里面的k
之前的物品,即f[i][j][k-1]
。
3. 选当前第i
组里面的第k
个物品,即f[i-1][j-v[i][k]][s[i-1]]+w[i][k]
。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n, V, v[N][N], w[N][N], s[N], f[N][N][N];
int main() {
cin>>n>>V;
for (int i=1; i<=n; 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++) for (int j=1; j<=V; j++) for (int k=1; k<=s[i]; k++) {
f[i][j][k]=max(f[i-1][j][s[i-1]], f[i][j][k-1]);
if (j>=v[i][k]) f[i][j][k]=max(f[i][j][k], f[i-1][j-v[i][k]][s[i-1]]+w[i][k]);
}
cout<<f[n][V][s[n]];
return 0;
}