算法 - 多重背包

2020-08-05 10:11:32

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

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

题目描述：

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

PS: 完全背包和01背包的区别就是01背包只能选一件，完全背包可以选无数件

闫氏DP法：

PS: 多重背包问题和完全背包类似，这里是指从k件物品变成到了s[i]件物品。

所以伪代码同完全背包的最初版本：

1
2
3
4
5
for i <- 1 to n:
    for j <- 1 to m:
        for k <- 0 to s[i] and k * v[i] <= j:
            f[i][j] = max(f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i])

Python 实现如下：

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

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

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            k = 0
            while k <= s[i] and k * v[i] <= j:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i])
                k += 1

    print(dp[n][m])

main()

这代题的数据范围是 N <= 100, 所以用这样的暴力解法能过。

在下一道题 N <= 1000，这样的数据范围下，代码会超时。

所以会有一个二进制值优化：

比如一个数可以由2的倍数组成：

$2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8…$

比如数字7 = 1 + 2 + 3 = $2^0 + 2^1 + 2^2$

所以可以把s[i]最多分成$log s[i] + 1$份数， 然后再做01背包

比如s[i] = 7, 那么就可以分成$2^0 + 2^1 + 2^2$，然后在做01背包，那么选择的时候就可以选择:
1， 2， 4 那么最大就是7可以被选
1, 2 那么3就可以被选
1, 4 那么5就可以被选
2, 4 那么6就可以被选
1 那么1 就可以被选
2 那么2 就可以被选
3 那么3 就可以被选

这样就不用再一个一个从i = 0 枚举到s[i],此外还有个细节需要注意就是二进制$2^n <= s[i]$,当$2^n < s[i]$的时候需要把$s[i] - 2^n$剩余的也放入背包中

Python实现如下：

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
31
32
33
34

# 应为数据范围是N <= 1000, M <= 2000 所以做01背包的时候就是 N * M * log(M) ~= 20000多, 数据N = 25000 就不会超掉
N = 25000
dp = [0]*N
v = [0]*N
w = [0]*N

def main():
    n, m = map(int, input().split())
    cnt = 0
    for i in range(1, n + 1):
        a, b, c = map(int, input().split())
        temp = 1
        while temp <= c:
            cnt += 1
            v[cnt] = temp * a
            w[cnt] = temp * b
            c -= temp
            temp *= 2

        if c > 0:
            cnt += 1
            v[cnt] = c * a
            w[cnt] = c * b


    for i in range(1, cnt + 1):
        for j in range(m, v[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])

    print(dp[m])


main()