0-1背包问题

如果每种物品只有一个，则是0-1背包问题。

状态转移方程

由于每种物品仅有一个，可以选择装或者不装。

取出一个物品后，该物品的个数变成0，相当于用完了，物品种类减一，同时背包的容量减小了，因此这里的变量有两个，背包容量和物品种类。因此我们定义函数 $f(i, j)$ ，表示把前 $i$ 个物品装进容量为 $j$ 的背包可以获得的最大价值。

原子问题是 $f(i, 0)=0$ ，即背包容量为0时，能容纳的物品的最大价值为0
变量为物品种类 $i$ 和背包容量 $j$
函数的返回值为能容纳的物品的最大价值
可选的动作有 $2N$ 种：对每种物品 $i$ ，选或不选

因此，可以得出状态转移方程如下：

f(i,j)=\begin{cases} 0 & j=0 \\ \max\left\{f(i-1,j),f(i-1, j-w_i)+v_i\right\} & 0 \leq i < N \end{cases}

这个方程理解如下，把前 $i$ 个物品装进容量为 $j$ 的背包时，有两种情况：

第 $i$ 个物品不装进去，这时所得价值为 $f(i-1,j)$
第 $i$ 个物品装进去，这时所得价值为 $f(i-1, j-w_i)+v_i$

代码框架

根据状态转移方程，得出伪代码如下：

f = [ [0] * (W+1) for i in range(N)] # N*(W+1) 2D array
for i in range(N):
    for j in range(w[i], W+1):
        f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

内循环从右向左也可以：

f = [ [0] * (W+1) for i in range(N)] # N*(W+1) 2D array
for i in range(N):
    for j in range(W, w[i]-1, -1):
        f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

当内循环从右向左时，可以把二维数组优化成一维数组（又称为滚动数组¹）。伪代码如下：

f = [0] * (W+1)
for i in range(N):
    for j in range(W, w[i]-1, -1):
        f[j]=max(f[j],f[j-w[i]]+v[i])

空间复杂度由 O(NW)降到了 O(W)。

为什么可以优化成一维呢？当内循环从右向左时，二维矩阵f是从上到下，从右到左的顺序计算的，一个元素仅仅依赖正上方的元素和左上方的元素，不再依赖右边的任何元素，因此可以用 f[j]表示两种含义，在更新 f[j]之前，f[j]里保存的 f[i-1][j]，更新之后，f[j]里保存的是 f[i][j]。

使用了滚动数组后，状态转移方程变成了：

f(j)=\begin{cases} 0 & j=0 \\ \max\left\{f(j),f(j-w_i)+v_i\right\} & 0 \leq i < N \end{cases}

这个方程可以换一种角度理解， $f(j)$ 表示容量为 $j$ 的背包，能容纳的物品的最大价值：

当没有物品时，没有东西可以装，所以背包能装进去的最大价值为0
当新增第1个物品时，令它的重量是 $w_0$ , 价值是 $v_0$ , 此时子问题 $f(w_0)$ , $f(w_0+1)$ ,..., $f(W)$ 的答案都是 $v_0$ ，而 $f(0)$ , $f(1)$ , ..., $f(w_0-1)$ 这些子问题，因为背包容量太小，装不下，所以能容纳的最大价值都是0 。
当新增第2个物品时，如果不选它，那最大价值不变；如果选它，则能获取最大价值是 $f(W-w_1)+v_1$ ， $f(W-w_1)$ 表示容量为 $W-w_1$ 的小背包能装入的最大价值，这个子问题在上一步已经求出来了
依此类推，当新增第 $i$ 个物品时，如果不选它，那最大价值不变；如果选它，则能获取最大价值是 $f(W-w_i)+v_i$

0-1 背包问题是许多背包问题的基础，它的代码可以被复用，因此，这里抽象出一个处理单个物品的函数，方便代码复用。

# c, 物品系数，在0-1背包问题下为1
def zero_one_knapsack(f: List[int], i: int, c=1):
    for j in range(W, w[i]-1, -1):
        f[j]=max(f[j],f[j-c*w[i]]+c*v[i])

有了这个函数以后，0-1 背包问题的伪代码就可以这样写：

f = [0] * (W+1)
for i in range(N):
    zero_one_knapsack(f, i)

刘汝佳,算法竞赛入门经典，清华大学出版社，2009，第 169 页 9.3.3 节 ↩

状态转移方程​

代码框架​

Footnotes​

状态转移方程

代码框架

Footnotes