背包，是动态规划里一类典型的问题，主要有：01背包，完全背包，多重背包，混合背包，二维费用背包，分组背包，有依赖背包和泛化物品等。本文仅介绍最常（简）见（单）的三类背包问题，在此推荐阅读《背包九讲》。

01背包

背景

有N件物品和一个容量为V的背包。第i件物品占据的空间是Ci，其价值为Wi。求解背包最多能背走多少价值的东西？或背走最多价值的东西有几种组合？

分析

• 将大问题拆解为子问题 01背包的特点是每种物品就有一件，可以选择放或者不放。

• 定义子问题状态 F[i,v]表示前i件物品放入一个剩余容量为v的背包中，可获得的最大价值。

• 写出状态转移方程

  F[i,v]=max{F[i-1,v],F[i-1,v-Ci]+Wi}
  

  分析前i件物品的状态时，其实只用考虑前i-1件物品的状态，如果不放入第i件物品，状态保持不变为F[i-1,v]；如果放，则体积减小Ci，价值增加Wi。

• 实现

  完整代码见文末典例。

  伪代码如下：

F[0,0..v] <—— 0  #初始化视题而定，此处仅为例子。
for i <—— 1 to N  
  for v<—— Ci to V
    F[i,v] <—— max{F[i-1,v],F[i-1,v-Ci]+Wi}

优化

上述伪代码的时间复杂度和空间复杂度均为0(VN)，时间复杂度不能优化，那么空间复杂度能否优化到O(V)?

空间复杂度的优化，重点是降维。对于主循环，i由1到N，第i次循环结束时，如果F[v]能够表示我们定义的状态F[i,v]就能够优化空间。在状态转移方程中，F[i,v]由F[i-1,v]和,F[i-1,v-Ci]推导出来，只要第i次循环中，推导F[v]时能取到F[i-1,v],F[i-1,v-Ci]就可以了。

我们想一下，压缩空间时F[i,v]和F[i-1,v]都表示为F[v],那么如何在等式右边只取F[i-1,v]不涉及F[i,v]呢？非常明显，在每次循环v的值时，递减由大到小计算F[v]即可，压缩空间后的伪代码如下：

F[0,0..v] <—— 0  #初始化视题而定，此处仅为例子。
for i <—— 1 to N  
  for v <—— V to Ci
    F[v] <—— max{F[v],F[v-Ci]+Wi}

由于一维数组解01背包问题使用非常频繁，因此将处理一件01背包物品的过程抽象出来：

def ZeroOnePack(F, C, W)
  for v <—— V to C:
    F[v] <—— max{F[v],F[v-C]+W}

有了每一件的处理过程，整体01背包可以这样写：

F[0..V] <—— 0 #初始化视题而定，此处仅为例子。
for i <—— 1 to N
  ZeroOnePack(F, Ci, Wi)

如何初始化

初始化数组F，其实就是初始化在没有放任何物品时，背包的合法状态。

求最优解的背包问题中，通常有两种不同的设定，一种要求“恰好装满背包”，一种不要求必须装满。这两种问题在实现时，初始化条件不同。

1. 恰好装满：只有容量为0的背包不装任何物品合法，此时价值为0。其余容量的背包不装任何物品时，是不合法的状态，初始化为负无穷。

2. 不必恰好装满：最初无论容量多少，背包不装任何物品都合法。所有初始化状态为0。

完全背包

背景

有N种物品和一个容量为V的背包，每种物品可以取无数件。第i种物品的体积为Ci,价值为Wi。求解：背包最多能背走多少价值的东西？或背走最多价值的东西有几种组合？

分析

• 拆解子问题 每种物品有无数件，但是所取物品体积之和不能多于背包体积，因此第i种物品，我们可以取0到⌊V /Ci⌋件。

• 定义子问题状态 F[i,v]表示前i种物品放入一个剩余容量为v的背包中，可获得的最大价值。

• 写出状态转移方程

  F[i,v]=max{F[i-1,v-kCi]+kWi|0<=k*Ci<=v}

  就是把01背包中物品的两种取法扩展成⌊V /Ci⌋+1 种取法。

• 实现

  完整代码见文末。

  完全背包可以直接把第i种物品转化为⌊V /Ci⌋件体积及价值均不变的物品，使用01背包的方法求解。

优化

类似于01背包的优化，时间复杂度为O(VN)，空间复杂度为O(V)。

伪代码：

F[0,0..v] <—— 0  #初始化视题而定，此处仅为例子。
for i <—— 1 to N  
  for v <—— Ci to V
    F[v] <—— max{F[v],F[v-Ci]+Wi}

v变成了递增遍历？

和01背包空间优化后v的循环次序不同，完全背包中使用递增，由大到小循环。压缩空间时，01背包问题中为了避免选择同一件物品，因此必须递减遍历v。但是对于完全背包问题，F[v]的更新可能会需要重复选取第i种物品，因此必须使用递增次序遍历v。

抽象出处理一件完全背包物品的过程如下：

def CompletePack(F, C, W)
  for v <—— C to V
      F[v] <—— max{F[v],f[v-C]+W}

多重背包

背景

有N种物品和一个容量为V的背包。第i种物品最多可以取Mi件，每件占据的空间为Ci，价值为Wi。求解背包最多能背走多少价值的东西？或背走最多价值的东西有几种组合？

分析

• 拆分子问题 每种物品有Mi件，每次可以取0-Mi件，共Mi+1种取法。

• 定义子问题状态 F[i,v]表示前i种物品放入一个剩余容量为v的背包中，可获得的最大价值。

• 写出状态转移方程

  F[i,v]=max{F[i-1,v-kCi]+kWi|0<=k<=Mi}

就是把01背包的两种取法扩展成Mi+1种取法。

• 实现

  完整代码见文末。

  和完全背包类似，多重背包问题可以把第i种物品转换成Mi件01背包中的物品，使用01背包求解。但这不会降低时间复杂度。

优化

使用二进制转换降低复杂度，但是超过Mi的取法不能出现。具体方法是：第i种物品分解为若干件01背包中的物品，每件物品有一个系数，体积和价值均是原体积和价值乘以这个系数。系数分别为1，2，..., 2^k-1，Mi-2^k+1，k是满足Mi-2^k+1>0的最大整数，这样就不可能取多于Mi件第i种物品，第i种物品就被分成

了⌊logMi⌋+1件物品。处理一件多重背包中物品的过程为：

def MultiplePack(F, C, W, M)
  if C*M>=V
     CompletePack(F, C, W)
     return
   k <—— 1
   while k<M
      ZeroOnePack(kC, kW)
      M <—— M-k
      k <—— 2*k
   ZeroOnePack(C*M, W*M)

10s小题

N种物品，背包体积为V。第i种物品，体积为Ci，价值Wi，可以取[Ai,Bi]件，Ai<Bi(如第3种物品，可以取[4,8]件)。如何求最优解？

大家抽空想下思路就好，千万不要想复杂！

下面先来实战背包问题。

典例与总结

这三种背包问题非常类似，主要区别就在于每种物品可以取的数目不同，因此三种方法通常可以相互转换。我们将通过实例，来感受三者间的区别与联系。

Leetcode 40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.

• The solution set must not contain duplicate combinations.

Input: candidates = [10,1,2,7,6,1,5], target = 8

分析：

这是一个典型的01背包问题，背包体积为8，每个元素代表一种物品，可选可不选。由于元素的价值和体积相等，故问题可视为：求背包背走最多东西时的组合？

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort() #对元素进行排序
        dp=[set() for i in range(target+1)] #dp[i]表示体积为i时的组合
        dp[0].add(())
        for i in candidates:
            for j in range(target,i-1,-1): #从后往前更新，避免重复
                for prev in dp[j-i]:
                    dp[j].add(prev+(i,))
        return dp[-1]

Output:

[[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]]

多重背包解读

以输入candidates = [10,1,2,7,6,1,5], target = 8为例，元素1的Mi=2,其余元素Mi=1。

完全背包解读

输入中，如果任意一种元素 值*数目>背包体积，可以使用完全背包求解。

综合解法

对于整道题，先统计出每种物品可使用的数目，对于每一种物品选择相应的背包算法进行处理，代码如下：

def zeroOnePack(c,m,v,ans):  #01背包
    for i in range(m,c-1,-1):
        for s in ans[i-c]:
            ans[i].add(s+v)
def completePack(c,m,v,ans):  #完全背包
    for i in range(c,m+1):
        for s in ans[i-c]:
            ans[i].add(s+v)
def multiPack(c,n,m,ans):  #多重背包
    items=[]
    b=0
    while n>(1<<b):
        items.append(1<<b) #把一种物品拆分成多件物品
        n-=(1<<b)
        b+=1
    if n:
        items.append(n)
    l=[]
    for i in items:
        if len(l)>i:
            l=[]
        while len(l)<i:
            l.append(c)
        zeroOnePack(c*i,m,tuple(l),ans)
class Solution(object):
    def combinationSum2(self, candidates, target):
        dp=[set() for i in range(target+1)]
        dp[0].add(())
        z={}
        for c in candidates:
            if c not in z:
                z[c]=0
            z[c]+=1
        n=len(z)
        m=target
        for i in z:
            if i>m:
                continue
            if z[i]==1:
                zeroOnePack(i,m,(i,),dp)
            elif z[i]*i>=m:
                completePack(i,m,(i,),dp)
            else:
                multiPack(i,z[i],m,dp)
        return dp[-1]
    

怎么样？基本的背包算法是不是很容易掌握~

我们下期再见！