背包

发表于

[转载]整理自背包九讲

01背包问题

  • [题目]有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是C_i，得到的价值是W_i。求解将哪些物品装入背包可使价值总和最大
  • 基本思路：
    • 最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放
  • 子问题定义状态:
    • F[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值
    • 其状态转移方程便是： $F[i,v]=max{F[i−1,v],F[i−1,v−C_i] + W_i}$

  • 将前i件物品放入容量为v的背包中”这个子问题, 若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i−1件物品相关的问题

    • 如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为v的背包中”，价值为F[i−1,v]
    • 如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为v−C_i的背包中”，此时能获得的最大价值就是F[i−1,v−C_i]再加上通过放入第i件物品获得的价值W

  • 伪代码如下：

1
2
3
4
F[0,0..V]=0
for i=1 to N
  for v=C_i to V
    F[i,v] = max{F[i−1,v], F[i−1,v−C_i] + W_i}

优化空间复杂度

1
2
3
4
F[0..V]=0
for i=1 to N
  for v=V to C_i 
    F[v] = max{F[v], F[v−C_i] + W_i}

初始化的细节问题

  • “恰好装满背包”时的最优解
    • 在初始化时除了F[0,0]为0，其它F[0,1..V]均设为−∞，这样就可以保证最终得到的F[V]是一种恰好装满背包的最优解

  • 没有要求必须把背包装满

    • 初始化时应该将F[0,0..V]全部设为0

  • 初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了

完全背包问题

  • [题目]有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是C_i，得到的价值是W_i。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大

  • 基本思路：

    • 每种物品有无限件
    • 从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……直至取⌊V/Ci⌋件等
    • 按照解01背包时的思路，令F[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值
    • $F[i,v] = max{F[i−1, v−kC_i] + kW_i|0≤kC_i≤v}$
    • 有O(VN)个状态需要求解，求解每个状态的时间已经不是常数了，求解状态F[i,v]的时间是O(
      v C_i)，总的复杂度可以认为是O(NV ΣV/C_i)，比较大

一个简单有效的优化

  • 完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足C_i≤C_j且W_i≥W_j，则将可以将物品j直接去掉，不用考虑
    • 并不能改善最坏情况的复杂度
    • O(N2)地实现

转化为01背包问题求解

  • 最简单的想法是，考虑到第i种物品最多选⌊V/C_i⌋ 件，于是可以把第i种物品转化为⌊V/C_i⌋件费用及价值均不变的物品，然后求解这个01背包问题
    • 没有改进时间复杂度
    • 指明了将完全背包问题转化为01背包问题的思路：将一种物品拆成多件只能选0件或1件的01背包中的物品

  • 更高效的转化方法：把第i种物品拆成费用为C_i2^k、价值为W_i2^k的若干件物品，其中k取遍满足C_i2^k≤V的非负整数

O(VN)的算法

1
2
3
4
F[0..V]=0
for i=1 to N
  for v=C_i to V 
    F[v] = max(F[v], F[v−C_i] + W_i
  • 与01背包问题的伪代码只有v的循环次序不同而已

  • 01背包中要按照v递减的次序来循环是为了保证第i次循环中的状态F[i,v]是由状态F[i−1,v−C_i]递推而来; 保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果F[i−1,v−C_i]

  • 完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果F[i,v−C_i]，所以就可以并且必须采用v递增的顺序循环

  • 两层for循环的次序可以颠倒, 有可能会带来算法时间常数上的优化

多重背包问题

  • [题目]有N种物品和一个容量为V的背包。第i种物品最多有M_i件可用，每件耗费的空间是C_i，价值是W_i。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大

  • 基本算法：

    • 对于第i种物品有M_i+1种策略：取0件，取1件……取Mi件。令F[i,v]表示前i种物品恰放入一个容量为v的背包的最大价值，则有状态转移方程：
    • $F[i, v] = max{F[i−1, v−kC_i]+kW_i|0≤k≤M_i}$
    • 复杂度是O(VΣM_i)

转化为01背包问题

  • 把第i种物品换成Mi件01背包中的物品，则得到了物品数为ΣM_i的01背包问题

  • 复杂度仍然是O(VΣM_i)

  • 二进制的思想

    • 将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1,2,2^2…2^{k−1},M_i−2^k+1，且k是满足M_i−2^k+1>0的最大整数
    • 分成的这几件物品的系数和为M_i，表明不可能取多于M_i件的第i种物品
    • 这种方法也能保证对于0…M_i间的每一个整数，均可以用若干个系数的和表示
    • 正确性的证明可以分0…2^{k−1}和2^k…M_i两段来分别讨论得出
    • 将第i种物品分成了O(logM_i)种物品，将原问题转化为了复杂度为O(VΣlogM_i)的01背包问题

O(VN)的算法

  • 基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解

混合三种背包问题

  • [问题]如果将前面的三种背包问题混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解

01背包与完全背包的混合

  • 如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可
  • 复杂度是O(VN)
1
2
3
4
5
6
7
for i=1 to N 
  if 第i件物品属于01背包 
    for v=V to C_i 
      F[v] = max(F[v], F[v−C_i] + W_i)
  else if 第i件物品属于完全背包
    for v=C_i to V 
      F[v] = max(F[v], F[v−C_i] + W_i)

加上多重背包

  • 加上最多可以取有限次的多重背包式的物品，那么利用单调队列，也可以给出均摊O(VN)的解法
  • 不考虑单调队列算法，用将每个这类物品分成O(logM_i)个01背包的物品的方法也已经很优
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def ZeroOnePack(F,C,W)
  for v=V to C
    F[v] = max(F[v], f[v−C] + W)
def CompletePack(F,C,W)
  for v=C to V 
    F[v] = max{F[v], f[v−C] + W)
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 := 2k 
  ZeroOnePack(C·M,W·M)
for i=1 to N 
  if 第i件物品属于01背包
    ZeroOnePack(F,C_i,W_i)
  else if 第i件物品属于完全背包
    CompletePack(F,C_i,W_i)
  else if 第i件物品属于多重背包
    MultiplePack(F,C_i,W_i,N_i)

二维费用的背包问题

  • [问题]二维费用的背包问题是指：对于每件物品，具有两种不同的空间耗费，选择这件物品必须同时付出这两种代价。对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。

  • 设这两种代价分别为代价一和代价二，第i件物品所需的两种代价分别为C_i和D_i。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为W_i

  • 算法：

    • 费用加了一维，只需状态也加一维。设F[i,v,u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
    • $F[i,v,u] = max{F[i−1,v,u], F[i−1,v−C_i,u−D_i] + Wi}$

  • 优化空间复杂度的方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环，当物品有如多重背包问题时拆分物品

物品总个数限制

  • 有时“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取U件物品
  • 事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为U
  • 设F[v,u]表示付出费用v、最多选u件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0…V,0…U]范围内寻找答案

复整数域上的背包问题

  • 另一种看待二维背包问题的思路是：将它看待成复整数域上的背包问题。背包的容量以及每件物品的费用都是一个复整数
  • 常见的一维背包问题则是自然数域上的背包问题
  • 一维背包的种种思想方法，往往可以应用于二维背包问题的求解中，因为只是数域扩大了而已

分组的背包问题

  • [问题]有N件物品和一个容量为V的背包。第i件物品的费用是C_i，价值是W_i。这些物品被划分为K组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

  • 算法：

    • 每组物品有若干种策略：是选择本组的某一件，还是一件都不选
    • 设F[k,v]表示前k组物品花费费用v能取得的最大权值，则有：
    • $F[k,v] = max{F[k−1,v], F[k−1, v−C_i] + W_i|item \ i \in group \ k}$
1
2
3
4
for k=1 to K 
  for v=V to 0 
    for item i in group k 
      F[v] = max{F[v], F[v−C_i] + W_i}
  • 三层循环的顺序保证了每一组内的物品最多只有一个会被添加到背包中

有依赖的背包问题

  • [简化的问题]这种背包问题的物品间存在某种“依赖”的关系。物品i依赖于物品j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品

  • 算法：

    • 将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成
    • 按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件
    • 无法用状态转移方程来表示如此多的策略。事实上，设有n个附件，则策略有2^n+1个，为指数级

  • 考虑到所有这些策略都是互斥的（只能选择一种策略），所以一个主件和它的附件集合实际上对应于分组的背包问题中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和

    • 仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多

  • 考虑对每组内的物品应用一个简单有效的优化中的优化

    • 对于第k个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果
    • 可以对主件k的“附件集合”先进行一次01背包，得到费用依次为0…V−C_k所有这些值时相应的最大价值F_k[0…V−C_k]
    • 这个主件及它的附件集合相当于V−C_k+1个物品的物品组，其中费用为v的物品的价值为F_k[v−C_k]+W_k，v的取值范围是C_k≤v≤V
    • 原来指数级的策略中，有很多策略都是冗余的，通过一次01背包后，将主件k及其附件转化为V−C_k+1个物品的物品组，就可以直接应用分组的背包问题的算法解决问题了

较一般的问题

  • 依赖关系以图论中“森林”的形式给出。主件的附件仍然可以具有自己的附件集合。限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖

    • 可以用将每个主件及其附件集合转化为物品组的方式
    • 唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品
    • 若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值

  • 一种树形动态规划，其特点是，在用动态规划求每个父节点的属性之前，需要对它的各个儿子的属性进行一次动态规划式的求值

泛化物品

  • [定义]考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分
    配给它的费用而变化

  • 在背包容量为V的背包问题中，泛化物品是一个定义域为0…V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)

  • 一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w外，其它函数值都为0的一个函数

    • 完全背包中的物品，可以看成这样一个函数，仅当v被c整除时有h(v)=w·
      v/c，其它函数值均为0
    • 多重背包中重复次数最多为m的物品，对应的泛化物品的函数有h(v)=w·v/c仅当v被c整除且
      v/c≤n，其它情况函数值均为0

  • 一个物品组可以看作一个泛化物品h。对于一个0…V中的v，若物品组中不存在费用为v的物品，则h(v)=0，否则h(v)取值为所有费用为v的物品的最大价值

泛化物品的和

  • 给定了两个泛化物品h和l，要用一定的费用从这两个泛化物品中得到最大的价值

  • 对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品

  • 对于0…V中的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即

  • $f(v) = max{h(k)+l(v−k)|0≤k≤v}$

    • 这里的f是一个由泛化物品h和l决定的定义域为0…V的函数，也就是说，f是一个由泛化物品h和l决定的泛化物品

  • 将f定义为泛化物品h和l的和：h、l都是泛化物品，若函数f满足以上关系式，则称f是h与l的和。泛化物品和运算的时间复杂度取决于背包的容量，是O(V^2)

泛函？

背包问题的泛化物品

  • 一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品

  • 给定了所有条件以后，就可以对每个非负整数v求得：若背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品

背包问题问法的变化

……