背包问题

背包问题泛指一下这一种问题：

给定一组有价值和固定重量的物品，以及一个已知最大承重的背包，求在不超过背包最大承重量的前提下，能放进把背包里的物品的最大总价值。

这是一种典型的使用 动态规划 解决的问题，我们可以具体分成三个问题：

• 0-1 背包问题
• 完全背包问题
• 多重背包问题

0 - 1背包

0 - 1 背包指每一种物品只有一件，可以选择放或者不放。假设有n件物品，背包承重为C

对于这种问题，我们用一个二维数组 f[i][c]，其中i表示放入背包的是前i件物品，c表示背包的承重，f[i][c]表示当前状态放进背包里的物品最大价值，那么最终结果就是f[n][C]

动态规划有三个基本要素：最优子结构，边界条件 和 状态转移方程：

• 状态转移方程：对于第 i个物体，有两种可能，拿 或者 不拿。拿的话，则f[i][c] = f[i-1][c - w[i]] + v[i]，即在前i-1个物体，花销为c-w[i]的情况下，拿了第i个物体，同时花销多花了w[i]，收益增加了v[i]。不拿的话，则f[i][c] = f[i-1][c]，即在前i-1个物体，花销为c的情况下，不花w[i]，同时也没有收益。所以我们的状态转移方程为：

f[i][c] = f[i-1][c-w[i]] + v[i] if add ith item
f[i][c] = f[i-1][c] if not add ith item

• 最优子结构：我们的目的是为了获得最大的价值，所以最优子结构为：

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

• 边界条件：最开始我们的背包什么都没有，所以f[0][0] = 0，没有花销，同时也没有收益。当背包放满了，放不下了，我们也没法更新，所以 f[i][c] = f[i-1][c] if c < w[i]，最后返回f[n][C]

有了上面的几个条件，我么就可以开始写代码了：

def knapsack(v: List[int], w: List[int], n: int, C: int)  -> int:
  # w is the weight, v is the value, n is the number of item and m is the total cost affordable
  f = [[0] * n for _ in range(C + 1)] # generate array

  for j in range(1, C+1):
    if j >= w[0]:
      f[0][j] = v[0] # when c > w[0], we can at least put item 0 and get value v[0]  
    else:
      f[0][j] = 0

  for i in range(1, n):
    for j in range(1, C+1):
      if j < w[i]:
        f[i][j] = f[i-1][j]
      else:
        f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[[i]])

  return f[n-1][C]

我们用这样一个例子：总共有5个商品：a,b,c,d,e，重量为：2, 2, 6, 5, 4，价值为：6, 3, 5, 4, 6。背包可承载重量为10，我们可以得到下面的表格：

	W	V	0	1	2	3	4	5	6	7	8	9	10	备注
a	2	6	0	0	6	6	6	6	6	6	6	6	6	consider item a
b	2	3	0	0	6	6	9	9	9	9	9	9	9	consider item b
c	6	5	0	0	6	6	9	9	9	9	11	11	14	consider item c
d	5	4	0	0	6	6	9	9	9	10	11	13	14	consider item d
e	4	6	0	0	6	6	9	9	12	12	15	15	15	consider item e

所以最后返回 15，也就是把a,b,e放到包里，总共重量8，总价值15

我们来计算时间复杂度和空间复杂度。两个循环嵌套，所以时间复杂度为O(nC)，空间复杂度开了一个[n][C]的数组，所以也是O(nC), 我们可以接着优化。我们发现，每一行数组都只跟上一级数组有关，所以空间复杂度可以简化为O(2C),我们还可以进一步优化为O(C)，那就是 从后往前填数组，因为对于i次更新，只会追溯到i-1次更新数据中c以前的数据，这样就只用保留一行数组。实质上也就是用上一轮的数据来更新这一轮。

def knapsack(v: List[int], w: List[int], n: int, C: int)  -> int:
  f = [0] * (C + 1)

  for i in range(n):
    for j in range(C, w[i]-1, -1):
      f[j] = max(f[j], f[j - w[i]] + v[i])

  return f[C]

如果题目要求我们输出最优解，而不只是答案，我们需要保存么一次变化的值，用来回溯最优解。

如果固定背包必须装满，那么除了f[0]初始化为0，其他f[1~c]都要初始化为float('-inf')，可以理解为没要物体时，除了把背包容量为0，那么什么都不装刚好装满，如果背包容量大于0，则除了f[0]外我们那种情况都装不满，所以初始化为负无穷。

完全背包问题

完全背包问题就是每一个物体有无数件，假设有n件物品，背包承重为C

相比于0-1背包，我们每一件物体选取没有数量限制，那么我们可以取0,1,2, … 到最多C//w[i]，按照0-1把背包的分析，我们可以写出状态转移方程：

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

时间复杂度变为了$O(nC* \Sigma C // w[i])$，我们也有进行优化。

会想一下0-1背包中，第一层是从0到n-1，第二层从右到左。从右都左 是为了保证第i件物体一点从i-1件物体的撞状态而来，也就是说，考虑第i件物体时，依据的是一个一定没有选中过i-1件物体的结论。如果将第二层循环改成 从左到右 就变成选第i件物体时依然从拿过第i件物体的结论中递推。状态转移方程为：

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

所以代码为：

def complete_knapsack(v: List[int], w: List[int], n: int, C: int)  -> int:
  f = [0] * (C + 1)

  for i in range(1, n):
    for j in range(w[i], C + 1):
      f[j] = max(f[j], f[j - w[i]] + v[i])

  return f[C]

这个写法和0-1背包几乎完全一致，不过第二层循环变成了从左到右更新。

多重（有界）背包问题

如果限定物品i最多只能拿m[i]个，则问题称为有界或多重背包问题

与完全背包相似，我们可以写出状态转移方程：

f[i][j] = max(f[i - 1][j - k * w[i]] + k * v[i])  where 0<=k<=m[i]

此时时间复杂度为$O(C \Sigma m[i])$，一种简化的方法是将问题转化为物体数量为$\Sigma m[i]$的0-1背包问题，比如a有2个，每个价值为5，我们可以看作a1，a2两个物体，每个物体的价值是5。但时间复杂度还是$O(C \Sigma m[i])$。

我们尝试用二进制的思想来优化，将有m[i]个的第i件物体分成k+1组，每组一个系数，分别为$1, 2, 2^2, …, 2^{k-1}, m[i] - 2^k + 1$，k为保证最后一项大于0的最大整数，原本有m[i]件的第i件物体，被分成了log(m[i])件，每一件物体的价值和费用都乘以原来的系数倍，这样时间复杂度变成了$O(C \Sigma \log m[i])$

这样分组是为了保证0～m[i]中的每一个数都可以用新分组的系数组合而成，且不会超过m[i]，证明引用知乎专栏

首先看系数中除了最后一项的所有项，每一项都是2的次方，也就是说如果用二进制表示用它们组合可以得到$0$ ~ $2^k - 1$中的所有数，这样我们还剩下$2^k$~$m[i]$中的数需要表示，证明完成了一半；现在把最后一个系数加进来，我们发现它加上之前系数可以表示的最大值$2^k - 1$后得到的正是$m[i]$，我们可以想象先将所有系数全部取走，得到的便是$m[i]$，然后根据选择丢弃不需要的系数，我们便可以得到$m[i] - 2^k + 1$ ~ $m[i]$中的所有值（从$1$ ~ $2^k - 1$ 依次丢)，那么现在就剩下$0$ ~ $m[i] - 2^k$ 这些值需要表示，而现在只需要证明 $2^k - 1$ 比 $m[i] - 2^k$ 要大就行了，因为前面证明已经得到了 $0$ ~ $2^k - 1$ 之间的数，这个证明很简单，直接相减，然后利用 $m[i] - 2^k + 1 > 0$的性质就可以得证。

我们来写代码，我们要先抽象出0-1背包和完全背包，然后进一步定义MultilePack

def zeroOnePack(f, wi, vi, C):
  for j in range(C, wi - 1, -1):
    f[j] = max(f[j], f[j - wi] + vi)

def completePack(f, wi, vi, C):
  for j in range(wi, C + 1):
    f[j] = max(f[i], f[j - wi] + vi)

def multiplePack(f, wi, vi, mi, C):
  if mi * wi >= C:
    # can take all, like complete pack
    completePack(f, wi, vi, C)
    return
  # the rest is 0 - 1 pack
  k = 1
  while k < mi:
    zeroOnePack(f, wi * k, vi * k, C)
    mi -= k
    k *= 2
  # the rest
  zeroOnePack(f, wi * mi, vi * mi, C)

def multi_knapsack(v: List[int], w: List[int], m: List[int], n: int, C: int)  -> int:
  f = [0] * (C + 1)
  for i in range(n):
    multiplePack(f, w[i], v[i], m[i], C)

  return f[C]

混合背包

如果物品中三种情况都有，那么我们可以分三种情况就行了

def hybrid_knapsack(v: List[int], w: List[int], m: List[int], n: int, C: int)  -> int:
  f = [0] * (C + 1)
  for i in range(n):
    if (m[i] == 1):
      zeroOnePack(f, w[i], v[i], C)
    elif m[i] == INT_MAX:
      completePack(f, w[i], v[i], C)
    else:
      multiplePack(f, w[i], v[i], C)
  return f[C]

对于其他的，比如填满背包问题，找钱问题，我会在下一次的动态规划介绍中提出。