算法 - 完全背包

2020-08-05 10:11:32

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

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

题目描述：

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

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

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

闫氏DP法：

状态计算就是状态方程，所以： $ f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2v[i] + 2w[i],…
, f[i - 1][j - k*v[i] + k * w[i]) $ 这里$j - K * v[i] >= 0$

伪代码如下：

1
2
3
4
5
for i <- 1 to n:
    for j <- 1 to m:
        for k <- 0 to j - k*v[i] > 0:
            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 = [[0]*N for _ in range(N)], [0]*N, [0]*N

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

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            k = 0
            while 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()

在此进行优化一下：
$f[i][j] = max(f[i][j], f[i- 1][j – v] + w, f[i - 1][j - 2v] + 2w, … f[i - 1][j - kv] + kw)$
$f[i][j - v] = max(f[i][j - v], f[i- 1][j – 2v] + w, f[i - 1][j - 3v] + 2w, … f[i - 1][j - kv] + (k - 1)w)$

这里的运算是取最大值, 所以红框里面部分只相差一个w[i] 所以状态方程就可以写成为:
$f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])$

01背包状态方程式：
$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$

不同点在于01背包是i - 1， 而完全背包是i

所以伪代码如下(类似于01背包)：

1
2
3
4
5
6
for i <- 1 to n:
    for j <- 1 to m:
        f[i][j] = f[i - 1][j]
        if v[i] <= j:
            # 只是这里变成了i
            f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]

Python实现：

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

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

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

    print(dp[n][m])


main()

同样也可以优化为一维，由于是f[i][j]需要的是f[i][j - v[i]]的状态，所以，只需要在使用前计算更新计算过第i层就行了。只要从小到大开始枚举，那么所在层数的j - v[i]是更新过了的，也就是第i层

伪代码如下：

1
2
3
for i <- 1 to n:
    for j <- v[i] to m:
        f[j] = max(f[j], f[j - v[i]] + w[i]

代码和01背包的写法非常类似，只是循环一个是从前，一个是从后。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

N = 1010
dp, w, v = [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] = map(int, input().split())

    for i in range(1, n + 1):
        for j in range(v[i], m + 1):  # 只是这里和01代码有所不同
           dp[j] = max(dp[j], dp[j - v[i]] + w[i])

    print(dp[m])

main()