数据结构与算法基础——背包问题9讲(Scala实现)

  |   0 评论   |   1,187 浏览

我们有N种物品,物品i的重量为wi,   价格为Ci
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W

Knapsack.svg (1).png

0-1背包

问题描述

如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题。

样例数据

  • N=5

  • W=15

  • {w, c}={(12, 4), (1, 2), (4, 10), (1, 1), (2, 2)}

问题分析

假定w1, ..., wn和W都是正整数。我们将在总重量不超过W的前提下,前i种物品的总价格所能达到的最高值定义为F(i, v)。

状态转移方程为

F(i, v) = max{ F(i - 1, v), F(i - 1, v - wi) + ci}

F(i, v)表示将前 i 件物品放入容量为 v 的背包中,即“将前 i 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只和前 i - 1 件物品相关的问题。

如果不放第 i 件物品,那么问题就转化为“前 i - 1 件物品放入容量为 v 的背包中”,价值为F(i - 1, v);

如果放第 i 件物品,那么问题就转化为“前 i - 1 件物品放入剩下的容量为 v - w的背包中”,此时能获得的最大价值就是 F(i - 1, v - wi) 再加上通过放入第 i 件物品获得的价值 vi

考虑边际条件,可以得到F(i, v)的递推关系:

  • F(0v) = 0,此时没有物品工选择,因此价值为0

  • F(i, v) = F(i - 1, v),(wv)背包剩余容量不足以放下第i件物品,只能空着

  • F(i, v) = max{ F(i - 1, v), F(i - 1, v - wi) + vi},(wi ≤ v)

通过计算F(N, W)即得到最终结果。为提高算法性能,我们把先前计算的结果存入表中。因此算法需要的时间和空间都为O(nW)

代码

object Pack01Dp {
  val num = 5; // 物品数量
  val pack_capacity = 15; // 背包容量

  val weight = Array(0, 12, 1, 4, 1, 2) // 物品的重量
  val value = Array(0, 4, 2, 10, 1, 2) // 物品的价值
  val F = Array.ofDim[Int](num + 1, pack_capacity + 1) // 为方便表示,索引值+1

  /**
    * 将前N件物品,放入一个容量为V的背包,计算可获得价值
    *
    * @param N 物品数量
    * @param V 背包容量
    */
  def dp(N: Int, V: Int): Unit = {
    for (i <- 1 to N) {
      for (v <- 1 to V) {
        if (v < weight(i)) { // 背包容量不足以放下第i件物品
          F(i)(v) = F(i - 1)(v)
        } else { // 第i件物品可选则放或不放
          F(i)(v) = math.max(F(i - 1)(v), F(i - 1)(v - weight(i)) + value(i))
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {
    dp(num, pack_capacity)
    for (i <- 1 to F.length - 1) {
      printf("前%d个物品放入背包中的价值:", i)
      for (j <- 1 to F(i).length - 1) {
        print("\t" + F(i)(j))
      }
      println()
    }
    printf("将%d个物品放入容量为%d的背包,可以获得的价值为:%d\n", num, pack_capacity, F(num)(pack_capacity))
  }
}

输出

前1个物品放入背包中的价值: 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4

前2个物品放入背包中的价值: 2 2 2 2 2 2 2 2 2 2 2 4 6 6 6

前3个物品放入背包中的价值: 2 2 2 10 12 12 12 12 12 12 12 12 12 12 12

前4个物品放入背包中的价值: 2 3 3 10 12 13 13 13 13 13 13 13 13 13 13

前5个物品放入背包中的价值: 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15

将5个物品放入容量为15的背包,可以获得的价值为:15

运行结果分析


背包容量123456789101112131415
前1个物品000000000004444
前2个物品222222222224666
前3个物品222101212121212121212121212
前4个物品233101213131313131313131313
前5个物品234101213141515151515151515

我们来分析一下上面这个表格

  1. 蓝色行代表要将物品放入的背包容量

  2. 每一行代表将前i个物品放入背包,相对应的列代表要放入背包的容量

  3. 第一行绿色的部分表示物品重量(12)大于背包容量(≤11),因此价值为0,其他行类推;

  4. 第一行黄色部分代表虽然背包容量有剩余,但物品数不足,因此也只能空着,其他行类推;

  5. 右下角的单元代表的就是最大价值,为什么呢?因为此时物品数最多,背包容量也最大,选择也最多。

优化空间复杂度

我们上面用到了一个二维数组来保存计算的结果,能否只用一维数组来保存结果呢?

由状态转移方程知,F(i, v)的值只与F(i - 1, v)和F(i - 1, v - Ci)有关,也就是只与F(i - 1, V)这一行的F(i - 1, ≤v)部分有关。

实际上,这要求我们在同一行中同时保存F(i - 1)行和F(i)行的的数据,如果我们正序遍历V的话,就会覆盖掉F(i - 1)行的数据,则在计算F(i, v + 1)时就不能正常取到F(i - 1, v + 1)的值,因此,这要求我们逆序遍历V,这样就可以一维数据的后面往前更新。

代码

object Pack01DpLessSpace {
  val num = 5; // 物品数量
  val pack_capacity = 15; // 背包容量

  val weight = Array(0, 12, 1, 4, 1, 2) // 物品的重量
  val value = Array(0, 4, 2, 10, 1, 2) // 物品的价值
  val F = new Array[Int](pack_capacity + 1) // 为方便表示,索引值+1
  /**
    * 利用一维数组处理01背包问题
    * 将第i件物品放入容量为V的背包所获得的价值
    * @param V  数组容量
    * @param i  第i件物品
    */
  private def zeroOnePack(V: Int, i: Int) = {
    for (v <- (1 to V).reverse) {
      if (v < weight(i)) { // 背包容量不足以放下第i件物品
        F(v) = F(v)
      } else { // 第i件物品可选择放或不放
        F(v) = math.max(F(v), F(v - weight(i)) + value(i))
      }
    }
  }
  /**
    * 将前N件物品,放入一个容量为V的背包,计算可获得价值
    *
    * @param N 物品数量
    * @param V 背包容量
    */
  def dp(N: Int, V: Int): Unit = {
    for (i <- 1 to N) {
      zeroOnePack(V, i)
    }
  }

  def main(args: Array[String]): Unit = {
    dp(num, pack_capacity)
    for (i <- 1 to F.length - 1 ) {
      print(F(i) + "\t")
    }
    printf("\n将%d个物品放入容量为%d的背包,可以获得的价值为:%d\n", num, pack_capacity, F(pack_capacity))
  }
}

我们将利用一维数组处理01背包问题抽象为一个方法zeroOnePack(V: Int, i: Int),方便后续使用

输出


2	3	4	10	12	13	14	15	15	15	15	15	15	15	15	
将5个物品放入容量为15的背包,可以获得的价值为:15

初始化的细节问题

在求最优解的背包问题中,有两种不同的问法:要求背包恰好装满和不要求装满。

一种区别这两种问法的实现方法是在初始化的时候有所不不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了 dp[0] 为0, 其他dp[1...W]均设为−∞ ,这样就可以保证最终得到 dp[W] 是一种恰好装满背包的最优解

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将dp[0...W] 全部设为0。 

这是为什么呢?可以这样理解:初始化的dp 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可以在什么也不装的状态下被 “恰好装满” ,此时背包价值为0。其他容量的背包均没有合法的解,属于未定义的状态,所以都应该被赋值为 −∞ 。当前的合法解,一定是从之前的合法状态推得的

如果背包并非必须被装满,那么任何容量的背包都有一个合法解 “什么也不装”,这个解的价值为0,所以初始化时状态的值也就全部为0了。

代码

for (i <- 1 to F.length - 1) {
    F(i) = Integer.MIN_VALUE// 初始化为-无穷
}




运行结果

我们可以将其与上面的表格进行对比,可见随着背包容量的增加,获得的价值不一定是最大的,因为要求背包恰好装满

背包容量123456789101112131415
前1个物品-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+094-2.1E+09-2.1E+09-2.1E+09
前2个物品2-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+0946-2.1E+09-2.1E+09
前3个物品2-2.1E+09-2.1E+091012-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+0946-2.1E+09-2.1E+09
前4个物品23-2.1E+09101213-2.1E+09-2.1E+09-2.1E+09-2.1E+09-2.1E+09467-2.1E+09
前5个物品2341012131415-2.1E+09-2.1E+09-2.1E+094678


完全背包

问题描述

有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。放入第 i 种物品的费用是 Ci,价值是 Wi。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包容量,且价值总和最大

这个问题非常类似于 01 背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取 0 件、取 1 件、取 2件……直至取 ⌊V /Ci⌋ 件等许多种。

转换为01背包问题求解

01背包问题是最基本的背包问题,我们可以考虑把完全背包问题转化为01背包问题来解。

最简单的想法是,考虑到第i种物品最多选⌊V/Ci⌋件,于是可以把第i种物品转化为⌊V/Ci⌋件费用及价值均不变的物品,然后求解这个01背包问题。

更高效的转化方法是:把第i种物品拆成费用为Ci2k、价值为Wi2k的若干件物品,其中k取遍满足Ci2k≤V的非负整数。

这是二进制的思想。因为,不管最优策略选几件第i种物品,其件数写成二进制后,总可以表示成若干个2k件物品的和。这样一来就把每种物品拆成O(log⌊V/Ci⌋)件物品,是一个很大的改进。

状态转移方程

第i种物品最多选⌊V/Ci⌋件,我们记选择的每件物品的数量为ki, 则0≤ki≤⌊V/Ci

这里的k可分为两种情况,k=0和k≠0,也就是第i种物品不选,或者至少选1个。 

  • k=0时,即不选择第i种物品,F(i, v)=F(i - 1, v),

  • k≠0时,即至少选一个第i种物品,F(i, v)=F(i, v - k ×wi) + k × vi

注意,当k≠0时,与01背包的方程不一样,此处是先往背包中放入一个第i中物品,然后把问题转化成更小规模的问题。

这里考虑的是“再放一件第i中物品时获得的价值”

F(i, v) = max{ F(i - 1, v - k ×wi) + k × vi}(0≤ki≤⌊V/Ci⌋)
=max{ F(i - 1, v), F(i - 1, (v - wi) - (k - 1) ×wi) + (k - 1) × vi + vi }(0≤ki - 1≤⌊V/Ci⌋ - 1)
=max{ F(i - 1, v), F(i, v - wi ) + vi}

代码

object CompletePack {
  val num = 5; // 物品数量
  val pack_capacity = 15; // 背包容量
  val weight = Array(0, 12, 1, 4, 1, 2) // 物品的重量
  val value = Array(0, 4, 2, 10, 1, 2) // 物品的价值
  val F = new Array[Int](pack_capacity + 1) // 为方便表示,索引值+1
  /**
    * 利用一维数组处理完全背包问题
    * 将第i件物品放入容量为V的背包所获得的价值
    *
    * @param V 数组容量
    * @param i 第i件物品
    */
  private def completePack(V: Int, i: Int) = {
    for (v <- 1 to V) {
      if (v < weight(i)) { // 背包容量不足以放下第i件物品
        F(v) = F(v)
      } else { // 增加第i件物品
        F(v) = math.max(F(v), F(v - weight(i)) + value(i))
      }
    }
    F.foreach((x) => print(x + "\t"))
    println()
  }
  /**
    * 将前N件物品,放入一个容量为V的背包,计算可获得价值
    *
    * @param N 物品数量
    * @param V 背包容量
    */
  def dp(N: Int, V: Int): Unit = {
    for (i <- 1 to N) {
      completePack(V, i)
    }
  }
  def main(args: Array[String]): Unit = {
    dp(num, pack_capacity)
    //    for (i <- 1 to F.length - 1 ) {
    //      print(F(i) + "\t")
    //    }
    printf("\n将%d个物品放入容量为%d的背包,可以获得的价值为:%d\n", num, pack_capacity, F(pack_capacity))
  }
}

输出

image.png

可以看到,上面的算法与01背包的方程只有遍历V的顺序不同,为什么会这样呢?

01背包中考虑了选与不选第i件物品的情况,让 v 递减是为了保证第 i 次循环中的状态 F(i, v)是由状态 F (i - 1, v - Ci) 递推而来,也就是为了保证第i件物品只选择一次,而完全背包每件物品可选多件,考虑的是“加选一件第i件物品”,正需要一个已放入的第i件物品F (i, v Ci) ,因此采取了正序遍历V的策略

多重背包

问题描述

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 Mi 件可用,每件耗费的空间是 Ci,价值是 Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量,且价值总和最大

基本算法

因为对于第i种物品有Mi+1种策略:取0件,取1件……取Mi件。令F(i, v)表示前i种物品恰放入一个容量为v的背包的最大价值,则有状态转移方程:

F(i,v) = max{F(i−1, v − k ∗ Ci) + k ∗ Wi}(0≤k≤Mi

复杂度是O(VΣMi)。

和完全背包问题很类似,主要在于k值的范围

转化为01背包问题

多重背包问题,最简单的解法,就是转化成0-1背包问题。第ii 个物品有 mimi 个, 等价于有mimi 个相同的物品。但直接拆分成 mimi 件物品并不是最好的方法。我们可以利用二进制来拆分。例如第3件物品有3件,拆分成20+21这2件, 3以内的任何数字都可以通过这2种数字组合而成。

代码

object MultiplePack {
  val num = 5; // 物品数量
  val V = 15; // 背包容量
  val weight = Array(0, 12, 1, 4, 1, 2) // 物品的重量
  val value = Array(0, 4, 2, 10, 1, 2) // 物品的价值
  val m = Array(0, 4, 2, 3, 1, 2) // 物品的数量
  val F = new Array[Int](V + 1) // 为方便表示,索引值+1
  /**
    * 利用一维数组处理完全背包问题
    * 将第i件物品放入容量为V的背包所获得的价值
    *
    * @param V 数组容量
    * @param i 第i件物品
    */
  private def completePack(C: Int, W: Int) = {
    for (v <- C to V) {
      F(v) = math.max(F(v), F(v - C) + W)
    }
    F.foreach((x) => print(x + "\t"))
    println()
  }
  /**
    * 利用一维数组处理01背包问题
    * 将第i件物品放入容量为V的背包所获得的价值
    *
    * @param C 第i个物品的重量
    * @param W 第i个物品的价值
    */
  private def zeroOnePack(C: Int, W: Int) = {
    for (v <- (C to V).reverse) {
      F(v) = math.max(F(v), F(v - C) + W)
    }
    F.foreach((x) => print(x + "\t"))
    println()
  }
  /**
    * 利用二进制拆解将多重背包分解为01背包
    *
    * @param C 第i个物品的重量
    * @param W 第i个物品的价值
    * @param M 第i个物品的数量
    */
  def multiplePack(C: Int, W: Int, M: Int): Unit = {
    var m = M
    if (C * m >= V) { // 背包容量只能放一种物品,与完全背包相同
      completePack(C, W)
      return
    }
    var k = 1
    while (k < M) { // 将M件第i个物品进行二进制拆分
      zeroOnePack(k * C, k * W) // 放入k个第i件物品
      m = m - k
      k *= 2
    }
    zeroOnePack(C * m, W * M) // 处理剩余的拆解部分
  }
  /**
    * 将前N件物品,放入一个容量为V的背包,计算可获得价值
    *
    * @param N 物品数量
    * @param V 背包容量
    */
  def dp(N: Int, V: Int): Unit = {
    for (i <- 1 to N) {
      multiplePack(weight(i), value(i), m(i))
    }
  }
  def main(args: Array[String]): Unit = {
    dp(num, V)
    printf("\n将%d个物品放入容量为%d的背包,可以获得的价值为:%d\n", num, V, F(V))
  }
}

结果

image.png