背包问题

0-1背包问题

问题

n个物体，它们各自有重量和价值，给定一个有容量的背包，如何让背包里装入的物体价值总和最大？

例如：

物品数量：num=4， 背包容量： capacity=8

i	1	2	3	4
w(体积)	2	3	4	5
v(价值)	3	4	5	6

原理

对于任意第 i 个 物品，只可能存在两种可能: ①装进背包 or ②不装进背包。

在此之前先定义一些符号表示:

val(i, j) : 表示当前背包可用空间为j，前i个物品最佳组合对应的价值。

因此，可以得到这么一个递推关系式:

1. 当前物品装不下，j < w(i) val(i, j) = val (i - 1, j)

2. 能装下当前物品，j >= w(i) val(i, j) = max { val(i - 1, j - w(i)) + v(i), val(i - 1, j) }

构建表格

在理解了这个递归关系式后，我们根据这个关系式来填写如下的表格，首先呢初始化边界条件，即 val(0, j) = val (i, 0) = 0

img1.jpeg img2.jpeg

这里举几个典型的栗子吧

比如说 val(2, 2), 此时背包容量j = 2，而i为2的背包重量w(2)为3，此时装不下，所以val(2, 2) = val (1, 2) = 3;

再举个典型的例子，对于val(3, 4)，对于i= 3的背包，w(3) = 4，而此时背包容量为4，能够装得下，val(3, 4) =max { val(2, 4 - w(3)) + v(3), val(2, 4) } =max{ val(2, 0) + v(3), 4} = max{ 5, 4 } = 5;

就这样，按着之前我们推到的递推关系式来填写表格即可。

这是整个建立这张表的过程实现:

 /**
  * w[i] 第i个物品的重量
  * v[i] 第i个物品的价值
  */

 public void findMax() { //利用动态规划
    for (int i = 1; i < num; i++) { // 开始填写第 i 行，逐行填写
        for (int j = 1; j < capacity; j++) { // j 背包可装载的容量
            if (j < w[i]) { // 如果物品放不进背包
                val[i][j] = val[i - 1][j];
            } else { // 能放进背包
                v[i][j] = Math.max(val[i - 1][j - w[i]] + v[i], val[i - 1][j]);
            }
        }
    }
 }

回溯找出背包方案

在构建了表格后，我们已经模拟了整个程序执行的过程，这个过程记录了所有的步骤和相关信息。而我们从表格中能够得出的信息是，val(i ,j)的最大值其实就在val(4, 8)位置，也就是表格的最右下方。我们还得知道这个最大值的选择方案是什么，即我们的背包需要带上哪几个物品？

这就是我们进行回溯的意义了。

img3.jpeg

我们回溯的过程很简单，相当于从最后一个物品开始往回倒推，查看每一个物品是否被选择？

从最右下角的元素开始，对于每一个val(i, j) ，需要满足以下规则:

① val(i , j) = val(i - 1, j) ，说明没有选择第i个物品，转到val(i - 1, j)；

② val(i , j) ≠ val(i - 1, j)，则说明选择了第i个物品，转到val(i - 1, j - w[i]);

③ 重复以上步骤直到 i = 0 为止。

下面是回溯的实现:

 /**
  * i , j 分别为第i个物品 和 背包剩余空间j
  * res[i] 表示第i个物品是否被装 ，取值→ 0 / 1
  */
 public void traceBack(int i, int j) { // 回溯
    if (i > 0) {
        if (v[i][j] == v[i- 1][j]) { // 没有装此物品
            res[i] = 0;
            traceBack(i - 1, j);
        } else {
            res[i] = 1;
            traceBack(i - 1, j - w[i]);
        }
    }
 }

---

（未完待续）后面还将进行一些其他背包问题的分析，尽量全面一点吧...