笔记资料参考于闫神的 算法基础课 动态规划第一讲，十分推荐。

个人博客地址：动态规划第一讲：背包问题

背包问题概述

$N$ 件物品放入容量为 $V$ 的背包，求最大的价值。

常见的背包问题分为：01背包问题，完全背包问题

其中核心的问题还是 01背包问题，其余的背包问题都是基于01背包的变形。

01 背包

问题描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$ 。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

问题分析

动态规划问题一般可以从集合的划分的角度来进行思考，如下图所示：

因此：

$f[i][j]$ 就表示只从前 $i$ 个物品中选取，且总体积 $\leq j$ 的所有选法的集合中的最大值。

现在可以考虑集合的划分，分为两种：

• $f[i-1][j]$ ：不选择第 $i$ 个物品的集合中的最大值

• $f[i-1][j-v[i]]+w[i]$ ：选择第 $i$ 个物品的集合中的最大值

因此有状态转移方程：
$$ f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) $$

问题求解

if __name__ == "__main__":
    N, V = map(int, input().split())
    v = [0] * (N+1)
    w = [0] * (N+1)
    for i in range(1, N+1):
        v[i], w[i] = map(int, input().split())
    dp = [[0] * (V+1) for i in range(N+1)]
    for i in range(1, N+1):
        for j in range(0, V+1):
            dp[i][j] = dp[i-1][j]
            if (j >= v[i]): # 选择第 i 个物品需要小于总体积
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i])
    print(dp[N][V])

求解优化

很多的DP问题可以在空间上进一步的优化，即对原来的状态计算进行等价变形。

观察状态转移方程 f[i][j]=max{f[i-1][j], f[i-1][j-v[i]]+w[i]} 可以发现：

当前层的状态永远只依赖于上一层的状态，因此我们可以用户一维的状态 f[j] 来表示之前同样的状态。

在第 $i$ 次循环之前，f[j]=f[i-1][j]

在第 $i$ 次循环之后，f[j]=f[i][j]

因此我们的状态转移方程变为了 f[j]=max{f[j], f[j-v[i]]+w[i]}

注意：由于我们要保证 f[j-v[i]] 就相当于原来的 f[i-1][j-v[i]] ，所以我们的第二层循环需要改为逆序。

if __name__ == "__main__":
    N, V = map(int, input().split())
    v = [0] * (N+1)
    w = [0] * (N+1)
    for i in range(1, N+1):
        v[i], w[i] = map(int, input().split())
    dp = [0] * (V+1)
    for i in range(1, N+1):
        for j in range(V, v[i]-1, -1):
            dp[j] = max(dp[j], dp[j-v[i]] + w[i])
    print(dp[V])

完全背包问题

问题描述

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

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$ 。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

问题分析

完全背包问题在状态表示上和 01背包是一致的，也是用 $f[i][j]$ 表示从前 $i$ 种物品中选择，且容量不超过 $j$ 的选法集合中的最大总价值。

主要的区别是在状态计算上，完全背包问题在进行集合的划分时不再是分为选第 $i$ 间物品和不选第 $i$ 物品两类，而是划分为第 $i$ 种物品选择 0, 1, 2, …, k 间，共 $k-1$ 个集合。

因此状态转移方程为：

k = 0
while k * v[i] <= j:
    f[i][j] = max(f[i][j], f[i-1][j-k*v[i]]+k*w[i])

问题求解

N, V = map(int, input().split())
v = [0] * (N+1)
w = [0] * (N+1)
dp = [[0] * (V+1) for i in range(N+1)]

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, V+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][V])

求解优化

注意到，我们在求解集合 f[i][j] 时，有：

因此，我们可以将状态计算公式改写为：

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

优化后的代码为：

N, V = map(int, input().split())
v = [0] * (N+1)
w = [0] * (N+1)
dp = [[0] * (V+1) for i in range(N+1)]

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, V+1):
        # 可以发现和 01 背包问题十分相似
        dp[i][j] = dp[i-1][j]
        if j >= v[i]:
            dp[i][j] = max(dp[i][j], dp[i][j-v[i]]+w[i])
print(dp[N][V])

求解优化2

同 01 背包一样，完全背包问题也可以在空间上进一步优化，进行等价替换。

需要注意的一点是，状态计算的第二项是 dp[i][j-v[i]]+w[i] ，其中 j-v[i] 小于 j ，所以要先计算出 dp[j-v[i]]。优化后的代码如下：

N, V = map(int, input().split())
v = [0] * (N+1)
w = [0] * (N+1)
dp = [0] * (V+1)

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], V+1): # 和 01 背包问题的唯一区别
        dp[j] = max(dp[j], dp[j-v[i]]+w[i])
print(dp[V])

完全背包问题和01背包问题在代码上只有第二层循环的顺序不同。

多重背包问题

问题描述

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

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$，且最多有 $s_i$ 件 。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

问题分析

可以注意到，多重背包问题与完成背包的问题的唯一区别就是多重背包问题中每个物品的数目是有限个，因此我们只需要将完全背包中划分为 $k+1$ 个集合，修改成划分为 s[i]+1 个集合即可。

因此状态转移方程为：

k = 0
while k <= s[i] and k * v[i] <= j:
    f[i][j] = max(f[i][j], f[i-1][j-k*v[i]]+k*w[i])

问题求解

N, V = map(int, input().split())
v = [0] * (N+1)
w = [0] * (N+1)
s = [0] * (N+1)
dp = [[0] * (V+1) for i in range(N+1)]

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, V+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][V])

求解优化

多重背包问题的优化不能采用完全背包问题的优化方法，因为 f[i][j-v[i]] 和 f[i][j] 的后面的项不是等价的。

多重背包问题的一个经典优化方式是采用二进制的优化方法，即将一种包含多件的物品转化为每种仅包含一个的多种物品。例如对于一个包含 10 件的物品 i ，则可以划分为：

[1, 2, 4, 3] ，其对应的体积和价值则为：

[1*v[i], 2*v[i], 4*v[i], 3*v[i]]

[1*w[i], 2*w[i], 4*w[i], 3*w[i]]

注意：对物品件数采样二进制的划分方法是因为这样刚好凑齐该区间的任意的件数。

可以注意到，经过优化后实际上就是每种物品只有一件，实质上就是将多重背包问题转化为了 01 背包问题。

通过上述的优化方法，时间复杂度可以从 $O(N*V*S)$ 优化为 $O(N*V*\log(S))$

算法代码为：

M = 12010  # N*log(S) 的大小
N, V = map(int, input().split())
v = [0] * M
w = [0] * M
dp = [0] * (V+1)
cnt = 0
for i in range(1, N+1):
    a, b, s = map(int, input().split())
    k = 1
    while k <= s:
        cnt += 1
        v[cnt] = a * k
        w[cnt] = b * k
        s -= k
        k *= 2
    if s > 0:
        cnt += 1
        v[cnt] = a * s
        w[cnt] = b * s
# 01 背包问题的求解
n = cnt
for i in range(1, n+1):
    for j in range(V, v[i]-1, -1):
        dp[j] = max(dp[j], dp[j-v[i]]+w[i])
print(dp[V])