背包问题2例

2020-12-04

Java Algo

背包问题其实属于动态规划（ Dynamic Programming ）问题的一种。动态规划的手段是将大问题拆解为多个小问题，小问题解决之后，大问题也就随之而解。

背包问题的典型描述是：

给定n种物品和一背包。物品i的重量为wi，其价值为vi，背包的容量为c。
问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

引例 #

为了阐述问题方便，引用《算法图解》一书中关于此书的图解好了(没有比这更好的解释方法了)。首先引入问题：

假设你是一个小偷，有一个可以装下4磅东西的背包，你可以偷窃的商品有:

4磅的音响，价值3000
3磅的笔记本电脑，价值2000
1磅的吉他，价值1500

当然，这个问题很简单，就算是遍历所有的可能性，也不过8种而已($2^3$)，不过当商品的数量增加时，可能性是指数式增长的，所以这种计算方式的运算时间复杂度是$O(2^n)$。现在尝试使用动态规划的方法来解决问题。

动态规划算法从一个网格开始，如下表的空白部分表示了示例问题中需要填充的表格：

_重量	_价值	_商品 \ ^背包重量
4	3000	音响
3	2000	笔记本电脑
1	1500	吉他

比如音响行第1列表示重量为1的背包装入音响所能获取的最大价值，笔记本电脑行第2列的表示重量为2的背包装入音响和笔记本电脑所能获取的最大价值...以此类推。现在我们尝试填充此表格，按照行的顺序

音响行
根据音响的重量，我们很容易就知道，重量为1、2、3的背包无法装下音响，当背包重量为4时，可以装下音响，此时的价值是3000，所以音响行填充完毕后，表格应该长这样：
_重量 _价值 _商品 \ ^背包重量 ¹ ² ³ ⁴
4 3000 音响 0 0 0 3000
3 2000 笔记本电脑
1 1500 吉他
笔记本电脑行
接下来继续填充笔记本电脑行，记住，此时背包可以选择的物品有音响和笔记本电脑2种。
- 当背包重量为1、2时，装不下笔记本电脑和音响中的任意一件商品，最大价值为0；
- 当背包重量为3时，不放入笔记本电脑时的最大价值为0（上一行已经计算得知），当放入笔记本电脑时，获得笔记本的电脑的价值2000，其剩余重量为0，无法装入音响；2000>0，因此背包重量为3时获得的最大价值就是2000；
- 当背包重量为4时，不放入笔记本电脑获得的最大价值是3000，当放入笔记本电脑时，获得笔记本的电脑的价值2000，其剩余重量为1，由音响行的计算结果可知，当背包重量为1时获得的最大价值是0（音响行第一列的值）；3000>2000+0，因此背包重量为3时获得的最大价值就是3000；
所以填充第二行之后的表格长这样：
_重量 _价值 _商品 \ ^背包重量 ¹ ² ³ ⁴
4 3000 音响 0 0 0 3000
3 2000 笔记本电脑 0 0 2000 3000
1 1500 吉他
吉他行
接下来填充吉他行，此时，背包可以选择的物品有音响、笔记本电脑和吉他3种。
- 当背包重量为1时，恰好可以装入吉他，因此其获得的最大价值就是1500；
- 当背包重量为2时，不放入吉他所能获得的最大价值是0，装入吉他之后，其获得价值1500；剩余重量为1，装入笔记本电脑和音响的最大价值就是0（笔记本电脑行的第1列）；因此最大价值是1500；
- 当背包重量为3时，不放入吉他所能获得的最大价值是2000，装入吉他之后获得价值1500，剩余重量为2，装入笔记本电脑和音响所能获取的最大价值是0（笔记本电脑行的第2列）；因此最大价值是2000；
- 当背包重量为4时，不放入吉他所能获取的最大价值是3000，装入吉他之后获得价值1500，剩余重量为3，装入笔记本电脑和音响所能获取的最大价值是2000（笔记本电脑行的第3列），1500+2000>3000，故获得的最大价值是3500
所以填充第三行之后的表格长这样：
_重量 _价值 _商品 \ ^背包重量 ¹ ² ³ ⁴
4 3000 音响 0 0 0 3000
3 2000 笔记本电脑 0 0 2000 3000
1 1500 吉他 1500 1500 2000 3500

到此为止，表格填充完毕，从表格中可以直观地看到容量为4的背包所能获取的最大价值是3500。除此之外，还可以看到，表格的行从左至右，列从上至下（填充顺序）所获得的最大价值都是递增的（或维持不变），不可能出现最大价值变小的情况！同时，计算容量较小的背包的最大价值这个工作并没有白费，它将用来帮助快速计算大容量的背包所能获取的最大价值。

关于背包问题，行（商品）的顺序并不影响最终的结果。对上例而言，任意打乱行的顺序获得的结果都是一样的。

上例中，若在可选商品列表中添加一个重1磅，价值2000美元的IPhone，结果会如何呢？
我们可以在已完成的表格中继续添加一个IPhone行，得到的结果应该是这样的：

_重量	_价值	_商品 \ ^背包重量	¹	²	³	⁴
4	3000	音响	0	0	0	3000
3	2000	笔记本电脑	0	0	2000	3000
1	1500	吉他	1500	1500	2000	3500
1	2000	IPhone	2000	3500	3500	4000

如果新增一个商品，重量为1.5磅，价值为2000元，动态规划表应该如何变化呢？
只需要将动态规划表格的列粒度变为0.5，再重新规划即可

状态转移方程 #

对于商品而言，其只有2个状态：放入背包或者不放入背包。动态规划的过程就是计算出不同承重的背包所能装入的最大价值，当考虑是否应当将物品装入背包时，比较其装入背包和不装入背包2种情况下获得的最大价值即可得到该背包的最大价值。

我们可以使用一个二维数组dp[i][j]表示i件物品放入重量为j的背包所能获取的最大价值。

如dp[3][4]=3500表示3件可选物品，放入容量为4的背包所获得的最大价值为3500。

和前面讨论的一样，dp[i][j]的计算分为3步：

该物品不放入背包的最大价值 v1 = dp[i-1][j]
该物品放入背包的最大价值 v2 = vi + dp[i-1][j-wi]，其中
- vi表示物品i的价值
- dp[i-1][j-wi]表示前i-1件物品放入容量为j-wi的背包中获取的最大价值，wi为物品i的重量
比较v1和v2，取较大值作为dp[i][j]

综上，背包问题的状态转移方程可以总结为：

\[ dp[i][j] = Max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) \]

Java代码示例 #

了解了思路，我们就可以轻松地将其使用编程语言解释：

 1public class PackIssue {
 2
 3    public static void main(String[] args) {
 4        Good[] gs = new Good[]{
 5            null,
 6            new Good(5, 4000),
 7            new Good(1, 2000),
 8            new Good(4, 1500),
 9            new Good(2, 8000),
10            new Good(1, 7000),
11            new Good(2, 3000),
12        };
13        int N = 10; // 背包最大容量
14        // 物品数, 空一行是为了防止计算dp时数组指针越界
15        // 不然计算dp时i = 0需要单独讨论
16        int m = gs.length - 1;
17
18        // 最大价值表是一张N*m的二维表格，
19        // 表格的每一格数据dp[i][j]表示i件物品放入容量为j的背包中
20        // 所能获取的最大价值，这个最大价值的形成有2个条件：
21        // 物品i要么放入背包，要么不放入背包
22        // 典型的dp公式
23        // dp[i][j] = max{dp[i-1][j], dp[i-1,j-w[i]] + v[i]}
24        // N也无需从0开始，没有意义
25        int[][] dp = new int[m + 1][N + 1];
26        for (int i = 1; i < m + 1; i++) {
27            int w = gs[i].w;
28            for (int j = 1; j < N + 1; j++) {
29                if (j >= w) {
30                    dp[i][j] = Math.max(
31                        dp[i - 1][j],
32                        dp[i - 1][j - w] + gs[i].v
33                    );
34                } else {
35                    dp[i][j] = dp[i - 1][j];
36                }
37            }
38        }
39
40        for (int i = 1; i < m + 1; i++) {
41            for (int j = 1; j <= N; j++) {
42                System.out.printf("%5d\t", dp[i][j]);
43            }
44            System.out.println();
45        }
46        System.out.println(dp[m][N]);
47    }
48
49
50}
51
52class Good {
53    // 物品重量
54    int w;
55    // 物品价值
56    int v;
57
58    public Good(int w, int v) {
59        this.w = w;
60        this.v = v;
61    }
62}
63
64/* output
65   0	    0	    0	 3000
66   0	    0	 2000	 3000
671500	 1500	 2000	 3500
683500
69*///:~

例2 复杂的背包问题 #

这个问题发现自机试题库

王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为： v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中* 为乘号）

请你帮助王强设计一个满足要求的购物单。

输入描述:

输入的第 1 行，为两个正整数，用一个空格隔开：N m。（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号

输出描述:

输出一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。

示例输入：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

示例输出：

2200

这个问题和简单的背包问题有诸多类似，差别在于，每一个物品多了附件，因此计算dp[i][j]时需要考虑的情况变得复杂了。将主件+附件看作一个整体计算dp，问题也就得到解决了。

除了动态规划之外，这个题目的题干也给出了很多有用的信息（审题也很重要啊）：

每个主件只有至多2个附件；
每一行（n）输入的数据都有一个id（n-1）；
若q = 0 并不是其id为0，而是指示其是主件，其id由输入次序指定；
若q>0，指示其是附件，q的值是其主件的id，其id由输入次序指定；
物品价格是10的倍数——指定表格列的粒度

获取并理解上面的信息，对于构建模型和录入数据都是非常有利的。就使用示例输入来分析，示例输入了5个物品，id为1～5。其中id=2和id=3的物品为id=1的附件，id=4和id=5的物品为主件。

回归到背包问题，由于附件是绑定主件的，所以解题时直接将附件的价值归结到主件中，那么问题就变成了1000元购买3件物品所能获取的最大价值。而对应于每一个主件，其最大价值的组成有多种可能性，我们需要在所有的可能性中找出最大价值：

不买主件，dp[i][j] = dp[i-1][j]；
只买主件，dp[i][j] = dp[i-1][j-wi] + vi；
买主件+附件1，dp[i][j] = dp[i-1][j-wi-wa1i] + vi + va1i；
买主件+附件2，dp[i][j] = dp[i-1][j-wi-wa2i] + vi + va2i；
买主件+附件1+附件2，dp[i][j] = dp[i-1][j-wi-wa1i-wa2i] + vi + va1i + va2i；

以下是该问题的java语言解决方式：

  1public class PackIssue2 {
  2
  3    public static void main(String[] args) {
  4        Scanner in = new Scanner(System.in);
  5
  6        int N = in.nextInt(); // price limit
  7        if (N >= 32000) return;
  8        int m = in.nextInt(); // goods want buy
  9        if (m >= 60) return;
 10
 11        Tar[] tars = new Tar[m + 1]; // index from 1
 12
 13        for (int i = 1; i < m + 1; i++) {
 14            int v = in.nextInt();
 15            int p = in.nextInt();
 16            int q = in.nextInt();
 17            Tar tar = new Tar(v, p, q > 0);
 18            if (q > 0) {
 19                if (tars[q].a1 == 0) {
 20                    tars[q].setA1(i);
 21                } else {
 22                    tars[q].setA2(i);
 23                }
 24            }
 25            // add all goods to Tar[]
 26            tars[i] = tar;
 27        }
 28
 29        // dp
 30        int[][] dp = new int[m + 1][N + 1];
 31
 32        for (int i = 1; i < m + 1; i++) {
 33            Tar tar = tars[i];
 34            int vi = tar.v;
 35            for (int j = 10; j < N + 1; j += 10) {
 36                if (tar.isAttach) {
 37                    // skip attachments
 38                    dp[i][j] = dp[i - 1][j];
 39                    continue;
 40                }
 41                if (j >= vi) {
 42                    // only main
 43                    int dp1 = vi * tar.p;
 44                    int dp2 = dp1, dp3 = dp1, dp4 = dp1;
 45                    int lv2 = vi, lv3 = vi, lv4 = vi;
 46                    int lj = j - vi;
 47                    // main + attachment1
 48                    if (tar.a1 > 0) {
 49                        Tar a1 = tars[tar.a1];
 50                        if (lj >= a1.v) {
 51                            dp2 += a1.v * a1.p;
 52                            lv2 += a1.v;
 53                        }
 54                    }
 55                    // main + attachment2
 56                    if (tar.a2 > 0) {
 57                        Tar a2 = tars[tar.a2];
 58                        if (lj >= a2.v) {
 59                            dp3 += a2.v * a2.p;
 60                            lv3 += a2.v;
 61                        }
 62                    }
 63                    // main + attachment1 + attachment2
 64                    if (tar.a1 > 0 && tar.a2 > 0) {
 65                        Tar a1 = tars[tar.a1];
 66                        Tar a2 = tars[tar.a2];
 67                        if (lj >= a1.v) {
 68                            dp4 += a1.v * a1.p;
 69                            lj -= a1.v;
 70                            lv4 += a1.v;
 71                            if (lj >= a2.v) {
 72                                dp4 += a2.v * a2.p;
 73                                lv4 += a2.v;
 74                            }
 75                        }
 76                    }
 77                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vi] + dp1);
 78                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - lv2] + dp2);
 79                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - lv3] + dp3);
 80                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - lv4] + dp4);
 81                } else {
 82                    dp[i][j] = dp[i - 1][j];
 83                }
 84            }
 85        }
 86        System.out.println(dp[m][N]);
 87    }
 88
 89
 90}
 91
 92class Tar {
 93    int v; // price
 94    int p; // priority, from 1-5
 95    boolean isAttach;
 96    int a1; // index of attachment 1 in Tar[]
 97    int a2; // index of attachment 2 in Tar[]
 98
 99    public Tar(int p, int w, boolean isAttach) {
100        this.v = p;
101        this.p = w;
102        this.isAttach = isAttach;
103    }
104
105    public void setA1(int a1) {
106        this.a1 = a1;
107    }
108
109    public void setA2(int a2) {
110        this.a2 = a2;
111    }
112}

xf&pl