跳到主要内容

0-1背包问题

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

状态转移方程

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

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

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

因此,可以得出状态转移方程如下:

f(i,j)={0j=0max{f(i1,j),f(i1,jwi)+vi}0i<Nf(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}

这个方程理解如下,把前ii个物品装进容量为jj的背包时,有两种情况:

  • ii个物品不装进去,这时所得价值为f(i1,j)f(i-1,j)
  • ii个物品装进去,这时所得价值为f(i1,jwi)+vif(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])

当内循环从右向左时,可以把二维数组优化成一维数组(又称为滚动数组1)。伪代码如下:

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)={0j=0max{f(j),f(jwi)+vi}0i<Nf(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)f(j)表示容量为jj的背包,能容纳的物品的最大价值:

  • 当没有物品时,没有东西可以装,所以背包能装进去的最大价值为0
  • 当新增第1个物品时,令它的重量是 w0w_0, 价值是 v0v_0, 此时子问题 f(w0)f(w_0), f(w0+1)f(w_0+1),..., f(W)f(W)的答案都是 v0v_0,而f(0)f(0), f(1)f(1), ..., f(w01)f(w_0-1)这些子问题,因为背包容量太小,装不下,所以能容纳的最大价值都是0 。
  • 当新增第2个物品时,如果不选它,那最大价值不变;如果选它,则能获取最大价值是 f(Ww1)+v1f(W-w_1)+v_1f(Ww1)f(W-w_1)表示容量为Ww1W-w_1的小背包能装入的最大价值,这个子问题在上一步已经求出来了
  • 依此类推,当新增第ii个物品时,如果不选它,那最大价值不变;如果选它,则能获取最大价值是 f(Wwi)+vif(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)

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