Knapsack - 背包问题

在一次抢珠宝店的过程中，抢劫犯只能抢走以下三种珠宝，其重量和价值如下表所述。

Item(jewellery) Weight Value
1 6 23
2 3 13
3 4 11

抢劫犯这次过来光顾珠宝店只带了一个最多只能承重17 kg的粉红色小包，于是问题来了，怎样搭配这些不同重量不同价值的珠宝才能不虚此行呢？哎，这年头抢劫也不容易啊…

用数学语言来描述这个问题就是：
背包最多只能承重 W kg, 有 n 种珠宝可供选择，这 n 种珠宝的重量分别为 \omega_1,\cdots,\omega_n, 相应的价值为 v_1,\cdots,v_n. 问如何选择这些珠宝使得放进包里的珠宝价值最大化？

Knapsack with repetition - 物品重复可用的背包问题

由于这类背包问题中，同一物品可以被多次选择，因此称为Knapsack with repetition, 又称Unbounded knapsack problem(无界背包问题).

动态规划是解决背包问题的有力武器，而在动态规划中，主要的问题之一就是——状态(子问题)是什么？在本题中我们可以从两个方面对原始问题进行化大为小：要么是是更小的背包容量 \omega \leq W, 要么尝试更少的珠宝数目(如珠宝 1, 2, \cdots , j, ~for~ j \leq n). 这两个状态(子问题)究竟哪个对于解题更为方便，还需进一步论证——能否根据状态(子问题)很方便地写出状态转移方程。

先来看看第一种状态：在背包容量为 \omega 时抢劫犯所能获得的最优值为 K(\omega). 对应此状态的状态转移方程并不是那么直观，先从 K(\omega) 所包含的信息出发，K(\omega) > 0 时，背包中必然含有某件值钱的珠宝，不妨假设最优值 K(\omega) 包含某珠宝 i, 那么将珠宝 i 从背包中移除后，背包中剩余珠宝的价值加上珠宝 i 的价值即为 K(\omega). 哪尼？这不就是个天然的状态转移方程么？抢劫犯灵机一动，立马想出了如下状态转移方程：
K(\omega) = F(\omega - \omega_i) + v_i ~(\omega_i \in \Omega)

其中 F(\omega - \omega_i) 为拿出珠宝 i 后的价值映射函数(用人话来说就是把粉红色小包里剩下的珠宝价值加起来)，取出来的珠宝重量 \omega_i < \omega(总不能取出大于背包重量的珠宝吧…), \Omega 即为 K(\omega) 中 \omega_i 的所有可能取值。想了想好像哪里不对劲，K(\omega) 的转移关系没鼓捣出来，反而新添了个 F(\omega - \omega_i), 真是旧爱未了又添新欢… 别急，再仔细瞅瞅以上等式两端，拿出珠宝 i 后，其价值 v_i 就可以认为是一个定值了，故要想 K(\omega) 为最大值，F(\omega - \omega_i) 也理应是背包容量为 \omega - \omega_i 时的包内珠宝的最大价值，如若不是，则必然存在 F(\omega - \omega_i) < K(\omega - \omega_i), 即有
K(\omega) = F(\omega - \omega_i) + v_i < K(\omega - \omega_i) + v_i = K^{\prime}(\omega)
与 K(\omega) 为在背包容量为 \omega 时的最大值的定义不符，故假设不成立，F(\omega - \omega_i) = K(\omega - \omega_i). 千斤顶终于成功上位——变成了备胎… 新的状态转移方程可改写为：
K(\omega) = K(\omega - \omega_i) + v_i

嗯，好像还是有哪里不对劲，千斤顶虽然已晋级为备胎，可备胎这个身份实在是不怎么好听，这不还有下标 i 这个标记嘛，我们给抢劫犯想想法子，怎么才能让备胎尽快转正呢？！仔细分析发现我们刚才取出d的价值 v_i 是从已知背包容量为 \omega 时取出来的珠宝 i, 重量为 \omega_i. 那么到底那几个珠宝才是可能被取出来的呢？答案不得而知，只知道肯定是小于背包容量 \omega 中的某一个。既然是这样，我们把所有小于背包容量 \omega 的珠宝挨个拿出来比一比不就完了么？但这样一来又有了新的问题：取出来的珠宝 \omega_i 不一定是最大值 K(\omega)中所包含的珠宝，那假如我们一定要拿出来比一比呢？得到的结果自然是不大于最大值 K(\omega)(如果不是，反证法证之), 用数学语言表示就是：
K(\omega) \geq K(\omega - \omega_j) + v_j ~(\omega_j \notin \Omega)

整理一下思路，用优雅的数学语言来表示就是：
K(\omega) = \max_{i:~\omega_i \leq \omega} {K(\omega - \omega_i) + v_i}

备胎终于得以登堂入室，警察叔叔，就是她了… 状态转移方程终于完整的找到了，千斤顶窃喜道：皇天不负有心人，我也有转正的一天，蛤蛤蛤…

令dp[i + 1][j]表示从前i种物品中选出总重量不超过j时总价值的最大值。那么有转移方程：

  1. dp[i + 1][j] = max{dp[i][j - k × w[i]] + k × v[i] | 0 ≤ k}

最坏情况下时间复杂度为 O(kW^2). 对上式进一步变形可得：

  1. dp[i + 1][j] = max{dp[i][j - k × w[i]] + k × v[i] | 0 ≤ k}
  2.              = max{dp[i][j], max{dp[i][j - k × w[i]] + k × v[i] | 1 ≤ k}}
  3.              = max{dp[i][j], max{dp[i][(j - w[i]) - k × w[i]] + k × v[i] | 0 ≤ k} + v[i]}
  4.              = max{dp[i][j], dp[i + 1][j - w[i]] + v[j]}

注意等式最后一行，咋看和01背包一样，实际上区别在于dp[i + 1][], 01背包中为dp[i][]. 此时时间复杂度简化为 O(nW).

Knapsack without repetition - 01背包问题

上节讲述的是最原始的背包问题，这节我们探讨条件受限情况下的背包问题。若一件珠宝最多只能带走一件，请问现在抢劫犯该如何做才能使得背包中的珠宝价值总价最大？

显然，无界背包中的状态及状态方程已经不适用于01背包问题，那么我们来比较这两个问题的不同之处，无界背包问题中同一物品可以使用多次，而01背包问题中一个背包仅可使用一次，区别就在这里。我们将 K(\omega) 改为 K(i,\omega) 即可，新的状态表示前 i 件物品放入一个容量为 \omega 的背包可以获得的最大价值。

现在从以上状态定义出发寻找相应的状态转移方程。K(i-1, \omega)为 K(i, \omega) 的子问题，如果不放第 i 件物品，那么问题即转化为「前 i-1 件物品放入容量为 \omega 的背包」，此时背包内获得的总价值为 K(i-1, \omega)；如果放入第 i 件物品，那么问题即转化为「前 i-1 件物品放入容量为 \omega - \omega_i 的背包」，此时背包内获得的总价值为 K(i-1, \omega - \omega_i) + v_i. 新的状态转移方程用数学语言来表述即为：
K(i,\omega) = \max {K(i-1, \omega), K(i-1, \omega - \omega_i) + v_i}

这里的分析是以容量递推的，但是在容量特别大时，我们可能需要以价值作为转移方程。定义状态dp[i + 1][j]为前i个物品中挑选出价值总和为j 时总重量的最小值（所以对于不满足条件的索引应该用充分大的值而不是最大值替代，防止溢出）。相应的转移方程为：前i - 1 个物品价值为j, 要么为j - v[i](选中第i个物品). 即dp[i + 1][j] = min{dp[i][j], dp[i][j - v[i]] + w[i]}. 最终返回结果为dp[n][j] ≤ W 中最大的 j.

扩展

以上我们只是求得了最终的最大获利，假如还需要输出选择了哪些项如何破？

以普通的01背包为例，如果某元素被选中，那么其必然满足w[i] > j且大于之前的dp[i][j], 这还只是充分条件，因为有可能被后面的元素代替。保险起见，我们需要跟踪所有可能满足条件的项，然后反向计算有可能满足条件的元素，有可能最终输出不止一项。

Java

  1. import java.util.*;
  3. public class Backpack {
  4.     // 01 backpack with small datasets(O(nW), W is small)
  5.     public static int backpack(int W, int[] w, int[] v, boolean[] itemTake) {
  6.         int N = w.length;
  7.         int[][] dp = new int[N + 1][W + 1];
  8.         boolean[][] matrix = new boolean[N + 1][W + 1];
  9.         for (int i = 0; i < N; i++) {
  10.             for (int j = 0; j <= W; j++) {
  11.                 if (w[i] > j) {
  12.                     // backpack cannot hold w[i]
  13.                     dp[i + 1][j] = dp[i][j];
  14.                 } else {
  15.                     dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
  16.                     // pick item i and get value j
  17.                     matrix[i][j] = (dp[i][j - w[i]] + v[i] > dp[i][j]);
  18.                 }
  19.             }
  20.         }
  22.         // determine which items to take
  23.         for (int i = N - 1, j = W; i >= 0; i--) {
  24.             if (matrix[i][j]) {
  25.                 itemTake[i] = true;
  26.                 j -= w[i];
  27.             } else {
  28.                 itemTake[i] = false;
  29.             }
  30.         }
  32.         return dp[N][W];
  33.     }
  35.     // 01 backpack with big datasets(O(n\sigma{v}), W is very big)
  36.     public static int backpack2(int W, int[] w, int[] v) {
  37.         int N = w.length;
  38.         // sum of value array
  39.         int V = 0;
  40.         for (int i : v) {
  41.             V += i;
  42.         }
  43.         // initialize
  44.         int[][] dp = new int[N + 1][V + 1];
  45.         for (int[] i : dp) {
  46.             // should avoid overflow for dp[i][j - v[i]] + w[i]
  47.             Arrays.fill(i, Integer.MAX_VALUE >> 1);
  48.         }
  49.         dp[0][0] = 0;
  50.         for (int i = 0; i < N; i++) {
  51.             for (int j = 0; j <= V; j++) {
  52.                 if (v[i] > j) {
  53.                     // value[i] > j
  54.                     dp[i + 1][j] = dp[i][j];
  55.                 } else {
  56.                     // should avoid overflow for dp[i][j - v[i]] + w[i]
  57.                     dp[i + 1][j] = Math.min(dp[i][j], dp[i][j - v[i]] + w[i]);
  58.                 }
  59.             }
  60.         }
  62.         // search for the largest i dp[N][i] <= W
  63.         for (int i = V; i >= 0; i--) {
  64.             // if (dp[N][i] <= W) return i;
  65.             if (dp[N][i] <= W) return i;
  66.         }
  67.         return 0;
  68.     }
  70.     // repeated backpack
  71.     public static int backpack3(int W, int[] w, int[] v) {
  72.         int N = w.length;
  73.         int[][] dp = new int[N + 1][W + 1];
  74.         for (int i = 0; i < N; i++) {
  75.             for (int j = 0; j <= W; j++) {
  76.                 if (w[i] > j) {
  77.                     // backpack cannot hold w[i]
  78.                     dp[i + 1][j] = dp[i][j];
  79.                 } else {
  80.                     dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
  81.                 }
  82.             }
  83.         }
  85.         return dp[N][W];
  86.     }
  88.     public static void main(String[] args) {
  89.         int[] w1 = new int[]{2, 1, 3, 2};
  90.         int[] v1 = new int[]{3, 2, 4, 2};
  91.         int W1 = 5;
  92.         boolean[] itemTake = new boolean[w1.length + 1];
  93.         System.out.println("Testcase for 01 backpack.");
  94.         int bp1 = backpack(W1, w1, v1, itemTake); // bp1 should be 7
  95.         System.out.println("Maximum value: " + bp1);
  96.         for (int i = 0; i < itemTake.length; i++) {
  97.             if (itemTake[i]) {
  98.                 System.out.println("item " + i + ", weight " + w1[i] + ", value " + v1[i]);
  99.             }
  100.         }
  102.         System.out.println("Testcase for 01 backpack with large W.");
  103.         int bp2 = backpack2(W1, w1, v1); // bp2 should be 7
  104.         System.out.println("Maximum value: " + bp2);
  106.         int[] w3 = new int[]{3, 4, 2};
  107.         int[] v3 = new int[]{4, 5, 3};
  108.         int W3 = 7;
  109.         System.out.println("Testcase for repeated backpack.");
  110.         int bp3 = backpack3(W3, w3, v3); // bp3 should be 10
  111.         System.out.println("Maximum value: " + bp3);
  112.     }
  113. }

Reference