4.1. 0/1 背包问题¶

0/1 背包问题可以这样定义：一个窃贼带着一个能装走赃物的背包进入实施抢劫的地点。这个背包对它能承受而不破裂的重量有一个指定的上限。这个承重上限被称为 CAP。撬开保险柜后，窃贼发现保险柜里有 N 件物品，每件物品都有特定的重量和价值（两者均为整数）。窃贼的目标是，在不超出重量上限 CAP 的前提下，使所拿物品的总价值最大。问题名称中的"0/1"二元限定词表示每件物品必须被完整地接受或拒绝，也就是说，窃贼不能把一件物品拆分。

解决这个问题的第一步是构造一个递归解法，然后看看能否用动态规划使该解法更高效。为了更深入地理解这个问题，将使用以下记号：

解决这个算法的关键在于，对所有 i <= N、c <= CAP 递归地定义 V(i, c)。注意，当 V(i, c) 中的 i = N 且 c = CAP 时，问题就已经解决了。

要为这个问题创建解法，最好从简单的情况开始。考虑当 i = 1 时如何定义 V(i, c)。在这种情况下，我们要求的是在只涉及第一件物品、背包容量为 c 时，最优解的总价值。V(i, c) 的一个定义是：

另一个要考虑的简单情况是 i = 0 或 c = 0。如果 i = 0，没有任何物品需要考虑，所以 V(0, c) = 0。如果 c = 0，背包装不下任何别的东西，所以 V(i, 0) = 0。

接下来考虑当 i > 1 时，如何用较小的参数值来定义 V(i, c)。一个好的分解方式如下：

1. 如果 WT(i) > c，那么 V(i, c) 必须等于 V(i-1, c)，因为背包的容量不足以装下物品 i。

2. 否则，要确定解中是否包含物品 i，我们必须比较：

   1. A) 只用物品 1,2,3 ... i-1 时、容量为 c 的情况下的最优解，即 V(i-1, c))

   2. B) V(i-1, c-WT(i)) + VALUE(i) 的最优解。

      为什么是这样？如果物品 i 被装入背包，背包的剩余容量就会减少 WT(i)。所以 V(i-1, c-WT(i)) 表示在这个新容量下，从剩余物品中能获得的最佳价值。由于我们把物品 i 装入了背包，所以要加上 VALUE(i)。因此，如果取第 i 件物品，V(i-1, c-WT(i)) + VALUE(i) 就表示最优值。

      上面 (A) 和 (B) 中较大者，就是对于从 1, 2, 3, ..., i 中选取的物品、容量为 c 的问题的解。如果 (A) 较大，就不应把物品装入背包。如果 (B) 较大，就应把物品装入背包。如果两者相等，装与不装该物品都无关紧要。在本页其余部分的讨论中，如果 (A) 和 (B) 相等，则不把物品装入背包。在相等的情况下，取该物品或舍弃该物品都没有关系，因此为了保持一致，始终把它排除在解集之外。

利用上面给出的定义，该算法在类似 Java 的语言中的一种实现大致如下：:

//this function behaves like the V(i,c) method defined previously
//in this chapter 该函数的行为与本章前面定义的 V(i,c) 方法相同
int V(int i, int c){
    //base cases 基本情况
    if(i == 0 || c == 0){
        return 0;
    }
    //item does not fit case 物品放不下的情况
    if(wt(i) > c){
        return V(i-1, c);
    }
    //compare best case if item i is taken or left behind.
    //and return the larger number. 比较取走或舍弃物品 i 时的最优情况，
    //并返回较大的数值
    int B = V(i-1, c-wt(i)) + value(i);
    int A = V(i-1, c);
    if(A >= B){
        return A;
    }
    else{
        return B;
    }
}

这种递归方法的效率不会很好。对该算法的大多数调用，都会产生 2 次额外的递归调用，直到遇到基本情况为止。为了演示这一点，点击下面的显示按钮，查看该算法在一组三件物品上运行时产生的调用树的可视化。树中的每个结点都表示一次对 V(i, c) 的调用。从树中可以非常清楚地看出，该算法的效率是指数级的：O(2 ^ N)，其中 N 是物品的数量。

现在，考虑什么样的问题适合用动态规划求解。

• 问题的解最初以递归的方式构造。

• 解中所涉及的递归，通常会导致使用相同的函数参数值进行多次递归调用。也就是说，要解决原始问题，有必要多次计算特定的较小规模子问题的解。这几乎是所有可以应用动态规划的问题的关键。

• 递归函数返回的值的类型，可以存储在一个能够以函数关键参数为索引的数据结构中。这个数据结构可以用来存储先前计算过的子问题的解，从而用对先前计算值的快速 O(1) 召回，取代递归式的重新计算。

0/1 背包问题的递归解法完全满足上面全部三条准则。上面的调用树可视化清楚地表明有大量工作在重复进行。我们的 V(i, c) 返回的值是简单的整数，可以很容易地存储在二维数组中。下面的可视化展示了如何用动态规划大幅提高原始递归算法的效率。

需要注意的一件重要事情是，虽然这个算法能找到最优值，但它并不能找出产生该值的物品集合。要回答 0/1 背包问题，还需要做一些额外的工作。回想一下，A 和 B 两个值中较大者表明了针对某件特定物品所采取的动作。如果 A 较大或相等，那么该物品 不在 解集中。如果 B 较大，那么该物品 是 解的一部分。在下面的可视化中，从物品集合的完整最优值表中恢复出最优解集。

但是，如何轻易地得到一张完整的值表呢？回想一下，这两个函数调用是 V(i-1, c) 和 V(i-1, c-WT(i))。事实证明，表中的每一行只依赖它上面的一行。知道这一事实后，很容易看出可以用迭代方法来填充这张表。下面的代码展示了如何在类似 Java 的语言中生成这张表。:

int v(int n, int cap)
{
    int table[][] = new int[n+1][cap+1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= cap; j++){
            //base case 基本情况
            if(i == 0 || j == 0)
                table[i][j] = 0;
            else{
                //item wont fit case 物品放不下的情况
                if(wt(i) > j)
                    table[i][j] = table[i-1][j];
                else{
                    int A,B;
                    B = table[i-1][j-wt(i)] + value(i);
                    A = table[i-1][j];
                    if(A >= B)
                        table[i][j] = A;
                    else
                        table[i][j] = B;
                }
            }
        }
    }
    //some code could go here to recover the solution set.
    //这里可以添加一些代码来恢复解集

    //return the optimal value 返回最优值
    return table[i][j];
}

上面的算法创建了完整的表，并返回某个具体最优解的值。可以在算法末尾添加一小段代码，毫不费力地得到解的物品集。作为练习，试着修改上面的函数，使其获得并返回最优解集，并用你选择的语言实现它。上面算法的效率是 O(N * CAP)，因为填充表中的每个格子只需要常数时间的工作。与原来 O(2 ^ N) 的效率相比，这是一个巨大的改进。

提供了一系列练习，帮助你检验对 0/1 背包算法的掌握程度。如果手边有草稿纸，其中一些练习会更容易完成。

4.2. 练习 2¶

下一个练习要求你填满表中的一整行。请以由空格或逗号分隔的整数列表的形式输入答案。点击表中的某个格子会高亮该格子，让你在继续填写时能记住自己的位置。

4.3. 练习 3¶

在这个练习中，你必须确定能产生最优解的正确物品集合。要选择一件物品，请点击左侧物品表中该物品所在的那一列。你也可以像上一个练习那样，在主表中选择格子。

4.4. 练习 4¶

作为最后一个熟练度练习，你需要从"选项"列表中选择值，并把它们放到表中正确的位置。你必须按照递归算法填格时所用的顺序来选择，否则你的成绩不会提高。你可以随时单击计分按钮查看自己的成绩。如果犯了错误，可以随意多次使用撤销按钮。单击重置按钮可以生成一组新的数据。