三种背包问题（0-1背包、完全背包、多重背包）

2025-11-07

碎碎念

NYUSH ICDS 的作业考到了这一算法，经过一分钟的思考（真的只是一分钟），发现自己还是凭借之前信竞的优秀经验积累给出了代码，可喜可贺（）

下面就来讲一下背包问题，以防自己再忘记，也以防万一下学期可能需要给别人讲。

感谢参考文献：三种背包问题 - Sera Masumi's Docs。

什么是背包问题？

简单来讲，你有一个背包，它的容量为 $m$ ，你同时有若干个物品，它们有各自的体积和价值，将哪些物品装入背包可以使得它们的总体积和不超过背包的容量而总价值和最大？

我们把形如这样的一类与背包有关的问题称为背包问题。

0-1背包

问题描述

现有 $n$ 种物品和一个容量为 $m$ 的背包，第 $i$ 种物品的体积为 $cap[i]$ ，价值为 $val[i]$ ，每种物品只有一个，求在不超过背包容量限制的情况下所能获得的最大物品价值和为多少？

为什么不能使用贪心算法

看到这个问题，直觉上我们会想到计算每个物品的单位价值 $val[i] / cap[i]$ ，然后优先选择单位价值高的物品放入背包，直到背包不能再放入新的物品为止。

但是这样的做法并不总能得到最优解，比如说，假设背包容量为 $10$ ，有两种物品：

物品 A：体积 $10$ ，价值 $10$
物品 B：体积 $1$ ，价值 $9$

按照上面的方法，我们会优先选择物品 B，然后物品 A 就放不下了。

简单的解法

要解决这个问题，我们可以一件一件物品来考虑。虽然最后我们只需要知道最大价值是多少，但在尝试放入每件物品时，我们需要知道背包中除了这件物品外已经放入的物品所能获得的最大价值，所以我们需要记录背包已装入任意体积的物品时的最大价值。

首先，我们定义 dp[i][j] 表示前 i 种物品放入容量为 j 的背包所能获得的最大价值。初始时，dp 的每一项都为 0。

接下来，我们依次考虑每一种物品 i：

如果不放入物品 i，那么最大价值就是 dp[i - 1][j]
如果放入物品 i，那么最大价值就是 dp[i - 1][j - cap[i]] + val[i]（前提是 j >= cap[i]）

关键代码：

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(cap[i], m + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cap[i]] + val[i])
print(dp[n][m])

一维数组优化

不难发现，考虑第 i 种物品时，我们只依赖于 i - 1 种物品的状态。使用一个 $n$ 行的数组多少有一点浪费。

再进一步观察可以发现，在计算 dp[i][j] 时，我们只依赖上一行中索引小于等于 j 的元素，此时索引大于 j 的元素没有意义。

So What? 我们可以使用一维数组 dp[j] 来表示容量为 j 的背包所能获得的最大价值。为了保证在计算 dp[j] 时使用的是上一轮的状态，我们需要从后向前遍历容量 j：

dp = [0] * (m + 1)
for i in range(1, n + 1):
    for j in range(m, cap[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - cap[i]] + val[i])

为什么要倒序遍历？因为如果正序遍历，那么在计算 dp[j] 时，dp[j - cap[i]] 已经被更新过了，换言之物品 i 可能已经被放入了背包，这样在计算 dp[j] 时就可能导致同一件物品被多次放入背包。

完全背包

问题描述

现有 $n$ 种物品和一个容量为 $m$ 的背包，第 $i$ 种物品的体积为 cap[i]，价值为 val[i]，每种物品可以放入无限件，求在不超过背包容量限制的情况下所能获得的最大物品价值和为多少？

解法

在 0-1 背包使用一维数组的时候，我们需要倒序遍历容量 j，以防止同一件物品被多次放入背包。

那么聪明的你会发现，此时我们只要正序遍历容量 j 就可以满足完全背包的要求了！

dp = [0] * (m + 1)
for i in range(1, n + 1):
    for j in range(cap[i], m + 1):
        dp[j] = max(dp[j], dp[j - cap[i]] + val[i])

dp = [0] * (m + 1)
for i in range(1, n + 1):
    for k in range(num[i]):
        for j in range(m, cap[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - cap[i]] + val[i])

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)