背包问题是非常经典的动态规划问题，但是中文书籍和资料很少有把这个问题说得清晰明了的，问题表述不清，递推公式错误，不一而足，我在彻底想清楚这个问题后，觉得很有必要记录下整个思考过程。

原始问题

当前有$n$件物品，第$i$件物品的重量为$w_i$，价值为$p_i$，当前有一个容量为$C$的背包。此处物品的重量，价值以及背包的容量都是非负整数。从这些物品中精心挑选若干件装入包中，这若干件被挑选的物品总重量不超过背包容量$C$，总价值尽量大，那么所有可能的挑选方法得到的

1. 最大值为多少？
2. 放进去哪些物件得到这个最大值？

问题的表述比较抽象，如果上面的问题有统一的算法，那么即便问题的规模缩小，问题解决的逻辑也不会有变化，所以从规模比较小的情形入手，更容易分析出来。假设背包容量是4kg，我们有3件物品，每件物品的价格以及重量见下表

我相信大多数人看到这个问题，会使用如下的贪婪算法。

贪婪算法

1. 第1个想法是将物品按照价格从高到低进行排序，如果背包的空余容量可以容纳该物品，则将它放入背包。按照这个方法处理对于上面的例子，结果应该是仅仅放入第3件物品，价值是10，但是明显是错的，因为放入物品1和2的价值更大（17），所以这个方法行不通。

2. 与上面的方法类似，可以按照重量从轻到重装入背包，但是对于下面的情形一样行不通

放入背包的重量是物品1和2，总重是3，价值是17，正确答案是放入1和3，总价值是26，所以这种方法明显是错误的。

3. 另一种改进的方法，定义物品的价值密度为

$$ \rho_i = p_i/w_i $$ 按照价值密度由高到低排序，依次核验后放入背包，但是按照该算法处理下面的情形依然是失败的

该方法的结果是放入1和3，但是明显2和3号的价值更大。

所以，无论是按照重量，大小，还是密度排序，这样的方法都是错误的。其实考虑最周全的方法，求$n$件物品的是否放入背包的全部组合，记录所有总重量可以放入背包的组合的价值，然后选一个最大值即可，但是对于$n$件物品，需要考虑的组合有$2^n$组，算法的复杂度很高，当$n$比较大的时候就很不实际。

上面的三种方法使用贪婪算法，下面是《算法的乐趣》中对贪婪算法的描述，

贪婪算法是寻找最优解的常用方法，该方法将求解的过程分成若干步骤，在每个步骤都应用贪心原则，选取当前状态下最好的或者最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果是最好的或者最优的解。

之前的算法将物品的选择分解为依次挑选物品，这里的次序可以是价值从高到低，重量从低到高或者密度从大到小，并且希冀于每一步结束之后，整体上的价值是最高的，重量是最轻的或者密度是最大的。这个就是明显的贪婪算法思想，但是局部最优不等于全部最优，因此这样的算法是失败的。

动态规划

重新定义问题

重新思考这个问题，换一个角度将其理解为有限空间利用价值最大化的问题，我们更清晰的描述一下这个问题，有助于我们进一步思考。从$n$个物品中挑选出其中的$m(m \le n)$个，用于填充大小为$C$的空间，

1. 使得$m$个物件的的总重量不超过$C$，即$ \sum_{k=1}^{m}{w_k} \le C$
2. 在满足条件1的情况下，$m$个物件的总价值在所有可能的挑选组合中最大。

我们用$V[i, C]$表示这$m$个物件的总价值，即 $$ V[i,C] = \max_{s.t.}{\sum_{k=1}^{m}{p_k}}，m \le n $$ 重申一下$V[i,C]$的含义，它表示**使用$i$个物件充分填充空间$C$得到的最大价值，**所以，这个问题就需要找到两样答案，

1. $V[i,C]$的值；
2. 得到$V[i,C]$的值对应的$m$个物件的集合$M_i$

很多文章根本就没有把$V[i,C]$的含义说清楚！

很多文章根本就没有把$V[i,C]$的含义说清楚！

很多文章根本就没有把$V[i,C]$的含义说清楚！

请注意，这个含义非常重要，在后面的推导和计算过程中会反复使用，请务必深刻理解！

递推思路

注意前方高能，下面是这个算法的关键, 假定我们已经得到上面两个问题的答案，**如果此时再有第$i + 1$个物品加进来，该怎么处理？**此时，问题转换为求

1. 使用$i + 1$个物件充分填充空间C得到的最大价值$V[i + 1,C]$
2. 以及$V[i + 1,C]$对应的物件的组合$M_{i+1}$

当你手里拿着这个重量为$w_{i+1}$的物品，准备填充容量为$C$的空包时候（注意此处的空包，不要想当然得以为包里面已经有前面的$i - 1$中挑选的物件了），有下面两种情形，

1. 该物件的重量大于背包的容量，即$w_{i+1} \gt C$，那么这个物品无论如何也放不进背包，因此这个物品不会被选中，所以只能使用前面$i$个物件填充$C$，得出$V[i + 1,C] = V[i, C]，M_{i + 1} = M_{i}$。
2. 该物件的重量小于等于背包容量，即$w_{i+1} \le C$，这个时候你有两种选择，

• 先将这个物件放入背包，此处背包的可用空间还有$C-w_{i+1}$，那么可以使用之前的$i$件物品去充分填充这个剩余空间。注意，此时背包空间由两部分的物件充分填充，

  

  1. 物件$i+1$充分填充空间$w_{i+1}$，该空间的最大价值为$p_{i+1}$

  2. 之前的$i$个物件充分填充剩余的空间$C - w_{i+1}$，该空间的最大价值为$V[i-1, C-w_{i+1}]$ 所以，当前的情形下**使用$i+1$个物件填充空间$C$**的最大价值是上述二者的和，即$V[i+1, C] = V[i, C-w_{i+1}] + p_{i+1}，M_{i+1} = M_i\bigcup i+1$。

• 不放入背包，那结果和之前的第一种情形一样，空间$C$由前面的$i$件物品充分填充，那么$V[i + 1,C] = V[i, C]，M_{i + 1} = M_{i}$。 因此，结合上面的分析，对于这种可以放入背包的情形，取二者的最大值，有$V[i+1, C]=\max {V[i, C-w_{i+1}] + p_{i+1}，V[i, C]}$。

综合以上分析，我们得到了一个递推关系式，

**终于水落石出！**将递推关系式中的$i$换成$i-1$，于是得到如下的结果

初始条件及推导方法

根据上面的推导式，就可以求出最后的结果，最后还有两点需要明确：

1. $V[i, C]$的最初的值是什么？

   回想一下这个值表示的含义，使用$i$个物件充分填充空间$C$得到的最大价值，仔细考虑这个含义可以得到

   • $V[0,0] = 0$，使用0个物件填充大小为0的空间的最大价值肯定是0
   • $V[0,C] = 0$，使用0个物件填充大小为C的空间的最大价值肯定是0，背包空空如也，价值为0
   • $V[i,0] = 0$，使用$i$个物件填充大小为0的空间的最大价值肯定是0，背包空空如也，价值为0

2. 如何根据最初的值，一步步推导出最终的结果$V[i, C]$？

   再观察上面的递推公式，$i$个物件总的最大价值依赖于前$i-1$个物件总的最大价值以及当前第$i$个物件本身的重量以及价值，换句话说，如果我知道了前$i-1$个物件总的最大价值以及当前第$i$个物件本身的重量以及价值，那么我也能推导出$i$个物件总的最大价值。

   更仔细的观察公式里面的max的公式，我们不仅需要知道$V[i-1, C]$，还需要知道$V[i-1, C-w_i]$，特别地，这里的$w_i$表示第$i$个物件的重量，它可以是任意的非负整数，因此我们需要知道$V[i-1,0]$到$V[i-1,C]$的所有值，于是下面的二维数组填充就呼之欲出。

二维数组

我们使用二维数组记录$V[i,C]$，二维数组的行数为物件的总数$i$，二维数组的列数是背包的容量$C+1$（注意此处多加了一列，因为从上面的推导看出我们需要知道$V[i-1,0]$的值，所以多加一列作为第0列），我们使用之前的问题，使用4Kg容量的背包挑选下面的物件

我们一步步看看这个表格怎么填充，

1. 建立空的二维数组，行数是3，列数是5，表格中的所有值都是未知数（注意此表从第0列开始，我们数第0列，第1列直到第4列），

   

2. 根据之前的推论$V[i,0] = 0,i = 1,2,3$，所有行的第0列都是0，得到如下的表格

   

3. 计算第1行的值$V[1,k],k=1,2,3,4$，再回想一下这个含义的意思，使用1个物件填充空间为$k$的最大价值，第一个物件的重量是1，价值为8，那么

   • 可以填充大小为1的空间，填充后的剩余空间为0，总价值为8，即$V[1,1]= 8$；
   • 可以填充大小为2的空间，填充后的剩余空间为1，但是此时你手上没有别的物件了，所以填充到此为止，总价值为8，即$V[1,2]= 8$；
   • 可以填充大小为3的空间，填充后的剩余空间为2，但是此时你手上没有别的物件了，所以填充到此为止，总价值为8，即$V[1,3]= 8$；
   • 可以填充大小为4的空间，填充后的剩余空间为3，但是此时你手上没有别的物件了，所以填充到此为止，总价值为8，即$V[1,4]= 8$；

   于是，我们得到第一行的值如下表所示

   

4. 有了第2行的值，就可以根据之前的递推公式机械式得计算，第2件物品的重量为$w_2=3$，价值为$p_2=9$，

   • 第2件物品的$w_2>1$，所以根据递推公式计算$V[2,1]=V[1,1]=8$，这件物品不放入包中；
   • 第2件物品的$w_2>2$，所以根据递推公式计算$V[2,2]=V[1,2]=8$，这件物品不放入包中；
   • 第2件物品的$w_2=3$，所以根据递推公式计算$V[2,3]=\max {V[1, 3-w_2] + p_{2}，V[1, 3]}=\max {V[1,0] + 9，V[1, 3]}=9$，这件物品放入包中；
   • 第2件物品的$w_2<4$，所以根据递推公式计算$V[2,4]=\max{V[1, 4-w_2] + p_{2}，V[1, 4]}=\max{V[1, 1] + 9，V[1, 4]}=17$，这件物品放入包中；

   于是得到第二行的结果如下

   

5. 按照计算第2行值的方法，计算第3行的值，结果如下

   

   所以最终的结果是用3个物件填充空间为4的背包，得到的最大价值为$V[3,4] = 17$。

放入哪些物件

但是且慢，文章的开头还有一个问题，我们放进去哪些物件，得到这个最大值的呢？请注意之前的递推思路那一小节中的物件集合$M_i$的变化，当且仅当$V[i, C] = V[i-1, C-w{i}] + p_{i}$时，第$i$件物品才会被放进来。再仔细观察一下递推公式，我们可以看到$V[i,C]$的值要么等于$V[i-1, C-w{i}] + p_{i}$，要么等于$V[i-1,C]$，所以可以确认

如果$V[i, C] = V[i-1, C]$，那么第$i$件物品没有被放入背包中

但是仅仅有这个条件判断是不是已经足够了，如果第$i$个物品是被放入背包中的，下一步回溯还是考察$V[i-1,C]$是否与$V[i-2,C]$的值相等吗？回到之前的那幅图

总的问题与子问题有相同的结构，如果第$i+1$个物品已经验证放入背包中了，更小的问题是使用$i$个物件填充大小为$C-w_{i+1}$空间，那么我们应该考察$V[i,C-w_{i}]$是否与$V[i-1,C-w_{i}]$的值相等。所以回溯的算法如下：

1. 从二维数组的$V[i, C]$开始，检查$V[i, C]$的值是否与$V[i-1, C]$相同；
2. 考察第1步的结果

• 如果相同，那么第$i$件物品没有被放入背包，令$i-1\rightarrow i$，即继续检查$V[i-1, C]$的值是否与$V[i-2, C]$相同；

• 如果不同，那么第$i$件物品被放入背包，令$i-1\rightarrow i, C-w_i\rightarrow C$，即继续检查$V[i-1, C-w_i]$的值是否与$V[i-2, C-w_i]$相同；

3. 不停使用步骤2的逻辑，直到考察到$i=0$为止。

那么，就可以逐行倒着回溯二维数组，

1. 我们先看第3行，$V[3,4]=V[2,4]$，所以第3件物品没有放入背包；

   

2. 第2行，$V[2,4]\ne V[1,4]$，所以第2件物品放入背包，接下来需要检查$V[1,4-w_2]$是否与$V[0,4-w_2]$相同；

   

3. 第1行，$V[1,1]\ne V[0,1]$，所以第1件物品放入背包（注意此处$V[0,4] = 0$，二维表格没有第0行，但是我们初始条件中推导过这个值），检查结束。

编程代码

下面是C++的程序代码，

定义一个背包的类，默认有10物件，每个物件大重量为6，最高价格为35。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// knapsack.h
#include <iostream>
#include <vector>
#include <ctime>

using std::vector;
using std::cout;

typedef struct tagObj {
    int weight;
    int price;
} Obj;

inline int max(int a, int b) { return a > b ? a : b; }

class Knapsack
{
public:
    Knapsack(const int size = 10, const int maxWeight = 6, const int maxPrice = 35);
    void SolvePro(const int totalW);
    friend std::ostream& operator<<(std::ostream& os, const Knapsack& nap);
private:
    vector<Obj> knapsack_;
    vector<int> index_;
    int totalPrice_;
};

方法如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// knapsack.cpp
#include "knapsack.h"
#include <ctime>
#include <algorithm>

Knapsack::Knapsack(const int size, const int maxWeight, const int minPrice)
{
    srand(static_cast<unsigned int>(time(nullptr)));
    Obj obj;
    for (int i = 0; i < size; i++) {
         // 随机生成价值和重量
        obj.weight = rand() % maxWeight + 1;
        obj.price = rand() % minPrice + 1;
        knapsack_.push_back(obj);
    }
    totalPrice_ = 0;
}

std::ostream& operator<<(std::ostream& os, const Knapsack& nap)
{
    os << "Dispaly knapsack list\n";
    os << nap.knapsack_.size() << " object as below\n";
    for (unsigned i = 0; i < nap.knapsack_.size(); i++) {
        os << i + 1 << ": weight " << nap.knapsack_.at(i).weight << \
            ", price " << nap.knapsack_.at(i).price << "\n";
    }
    return os;
}

void Knapsack::SolvePro(const int totalW)
{
    const int row = static_cast<int>(knapsack_.size());
    const int col = totalW;
    vector<vector<int>> matrix(row + 1, vector<int>(col + 1, 0));
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            matrix[i][j] = matrix[i - 1][j];
            if (j >= knapsack_.at(i - 1).weight) {
                matrix[i][j] = max(matrix[i - 1][j], \
                    matrix[i - 1][j - knapsack_.at(i - 1).weight] + \
                    knapsack_.at(i - 1).price);
            }
        }
    }

    totalPrice_ = matrix[row][col];

    int startRow = row;
    int startCol = col;
    while (startRow > 0) {
        if (matrix[startRow][startCol] == matrix[startRow - 1][startCol]) {
            startRow--;
            continue;
        }

        index_.push_back(startRow);
        startCol -= knapsack_.at(startRow - 1).weight;
        startRow--;
    }

    reverse(index_.begin(), index_.end());

    cout << "\nWeight capacity is " << totalW << ", and totalPrice is " << matrix[row][col] << \
        ", selected obj index is: ";
    for (unsigned i = 0; i < index_.size(); i++) {
        cout << index_.at(i) << " ";
    }
    cout << "\n";
}

使用main函数，调用如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <iostream>
#include "knapsack.h"

int main()
{
    Knapsack nap1(10, 6, 10); // 我们有10个物品，最大重量为6，最大价值为10，价值和重量都是随机生成的
    std::cout << nap1;
    nap1.SolvePro(30); // 背包容量30
    return 0;
}

结果如下

参考资料

• 0-1背包问题 - 简书，描述《算法图解》中对该问题的解法，比较有趣
• 动态规划解决01背包问题 - Christal_R - 博客园，中文博客写得不错的文章
• 背包 DP - OI Wiki，在没有Google下搜索出来的总结比较全面的文章
• 背包问题九讲 · 看云，非常系统的背包问题的解释