背包，是动态规划里一类典型的问题，主要有：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，..., 2k-1，Mi-2k+1，k是满足Mi-2k+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]
怎么样？基本的背包算法是不是很容易掌握~
我们下期再见！
网友评论