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

原始问题

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

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

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

物品 1 2 3
重量/kg 1 3 4
价格/$ 8 9 10

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

贪婪算法

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

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

序号 1 2 3
重量/kg 1 2 3
价格/$ 8 9 18

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

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

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

序号 1 2 3
重量/kg 1 2 2
价格/$ 8 9 18
$\rho_i$ 8 4.5 9

该方法的结果是放入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]}$。

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

image-20200223120801234

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

image-20200223120832675


初始条件及推导方法

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

  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 2 3
重量/kg 1 3 4
价格/$ 8 9 10

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

  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]$相同;

  1. 不停使用步骤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。

// 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_;
};

方法如下

// 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函数,调用如下

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

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

结果如下

参考资料