算法 - 分组背包问题

2020-08-05 10:11:32

来源： https://www.acwing.com/problem/content/9/

推荐视频讲解： https://www.acwing.com/video/341/

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

闫氏DP法：

所以状态方程就是：

$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][n]] + w[i][n])$

C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int s[N], v[N][N], w[N][N];
int f[N];

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 0; 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 = 0; k < s[i]; 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;

}

Python实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N = 110
f, s = [0]*N, [0]*N
v = [[0]*N for _ in range(N)]
w = [[0]*N for _ in range(N)]

def main():
    n, m = map(int, input().split())
    for i in range(1, n + 1):
        s[i] = int(input())
        for j in range(s[i]):
            v[i][j], w[i][j] = map(int, input().split())

    for i in range(1, n + 1):
        for j in range(m, -1, -1):
            for k in range(s[i]):
                if v[i][k] <= j:
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k])

    print(f[m])

main()