背包问题

给定一组物品，每种物品都有自己的重量（体积）和价值，现有一个背包，在受限制的重量（或者容积）下，取若干物品，使得总价值最大。这一类问题，被称为背包问题。

题目描述

当前有 $N$ 件物品和一个承重量为 $V$ 的背包。已知第i件物品的重量是 $w[i]$，价值是 $v[i]$。

由于每种物品有且仅有一件，因此只能选择放或不放，我们称之为01背包问题。

现在你需要选出若干件物品，在它们的重量之和不超过C的条件下，使得价值总和尽可能大。

对于每个物品是否要装入背包，我们自然可以进行暴力枚举或搜索，但是如果要暴力地去做，那么时间复杂度会非常的高，这时候需要一种更加优化的算法——动态规划。

解析

对于 01 背包，先确定这个问题的状态。共有 $N$ 个物品，背包总承重为 $V$，那么可以根据物品和容量来确定一个状态。前 $i$ 个物品，放在背包里，总重量不超过 $j$ 的前提下，所获得的最大价值为 $dp[i][j]$。

是否将第 $i$ 个物品装入背包中，就是决策。为了使价值最大化，如果第 $i$ 个物品放入背包后，总重量不超过限制且总价值比之前要大，那么就将第 $i$ 个物品放入背包。根据这个逻辑写出转移方程：

$$ \begin{align*} \displaystyle \forall\ j < w[i], dp[i][j] &= dp[i-1][j]\ \displaystyle \forall\ w[i] \le j \le C, dp[i][j] &= max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i]) \end{align*} $$

为了更好地理解这个转移方程，看一个具体的例子。有 5 个物品，编号1-5，重量分别是 $[2,2,6,5,4]$，价值分别是 $[6,3,5,4,6]$，背包的总承重为 10。

列出本问题中所有的状态变量，也就是转移方程中的 $dp$ 变量，且初始化为0。当第一个物品放入背包，因为第一个物品重量为2，价值为6，只要背包容量大于等于2，都可以放第一个物品，根据我们的转移方程 $dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i]$ ，那么：

根据我们的转移方程继续放第二个物品，容量为2，3的时候： $dp[i-1][j-w[i]] + v[i] < dp[i-1][j]$ ，则 $dp[i][j] = dp[i-1][j]$ 。

容量大于3的时候： $dp[i -1][j-w[i]] + v[i] > dp[i-1][j]$ ，则 $dp[i][j] = dp[i-1][j-w[i]] + v[i]$ 。dp变量被更新为：

当放第3个物品的时候，第三个物品的重量 $w[i]=6$ ，所以在背包容量 $j<w[i]$ 的时候，$dp[i][j] = dp[i-1][j]$。在背包容量 $j \ge v[i]$ 的时候 $dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i])$。

以此类推，把剩余的物品全部根据转移方程放入背包后，dpdp 变量为：

通过上面的表格，可以知道当这 5 个物品放入容量为 10 的背包中，最大的价值是 15，也就是 $dp[5][10] = 15$。

 1for (int i = 1; i <= N; ++i) {
 2    for (int j = 0; j <= V; ++j) {
 3        if(j >= w[i]) {
 4            dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
 5        }
 6        else {
 7            dp[i][j] = dp[i-1][j];
 8        }
 9    }
10}

时间上是两重循环，时间复杂度为 $\mathcal{O}(NV)$。

空间是二维的，空间复杂度也为 $\mathcal{O}(NV)$。

优化空间复杂度

空间复杂度还可以优化到 $\mathcal{O}(V)$ ，但时间复杂度已经很难再优化了。

当前计算第 $i$ 件物品，总重量为 $v$ 的最大价值。我们注意到，它需要的状态是 $dp[i-1][0\ldots v]$ 。

如果从大到小，也就是从 $V$ 到 0 枚举，则当前引用的 $dp[v]$ 和 $dp[v-w[i]]$，仍然是计算第 $i-1$ 件物品的结果，即 $dp[i-1][v],dp[i-1][v-w[i]]$，那么这一维的状态是冗余的。

故我们可以化简转移方程：$dp[j]=max(dp[j-w[i]]+v[i],dp[j])$。

1for (int i = 1; i <= n; ++i)
2    for (int j = v; j >= w[i]; --j)
3        dp[j] = max(dp[j - w[i]] + v[i], dp[j]);

这个做法的空间复杂度为 $\mathcal{O}(V)$ 。