01背包问题解法

原创： Jiau 机器感知 8月7日

未经许可，禁止转载

1. 定义

我们有$N$种物品，物品$i$的重量为$w[i]$，价格为$p[i]$。我们假定所有物品的重量和价格都是非负的，背包所能承受的最大重量W，如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题 。

2. 二维动态规划解法

二维动态规划其实就是填表，表格中的值表示能获得的最大总价值，表格如下：

图片来源于国外的一个网站，网站地址见附录，感兴趣的可以去看看。

现在我们分析动态规划中的状态转移，假设当前待求状态为table[i][j]，其中，$i$表示第$i$个物品，$j$表示当前背包容量，由于是01背包问题，即一个物品只能选或者不选，也即当前最优解的可能有两种，即选与不选，对应的总价值分别为：table[i-1][j]、table[i-1][j-w[i]]+v[i]，解释如下：

当不选择第$i$件商品时，当前最大价值就和状态$i-1$，容量为$j$时的最优解一样；当选择第$i$件物品时，当前最大价值就状态$i-1$，但容量为$j-w[i]$，再加上当前物品价值$v[i]$时的价值，由此可得，该问题的状态转移方程如下：

table[i][j] = max(table[i-1][j], table[i-1][j-w[i]]+v[i])

有了这个状态转移方程之后，我们就可以写程序了，示例程序如下：

// total weight

#define W (18)

// total stuff

#define N (7)

int table[N+1][W+1] = {0};

int value[N+1] = {0, 12, 10, 8, 11, 14, 7, 9};

int weight[N+1] = {0, 4, 6, 5, 7, 3, 1, 6};

void knapsack()

{

int k, w;

for (k=1; k<=N; k++) {

for (w=1; w<=W; w++) {

if (weight[k] > w) {

table[k][w] = table[k-1][w];

} else {

int value1 = table[k-1][w-weight[k]] + value[k];

int value2 = table[k-1][w];

if (value1 > value2) {

table[k][w] = value1;

} else {

table[k][w] = value2;

}

}

}

}

}

运行结果如下，对比网图可知，结果完全相同：

3. 最优解回溯

通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表格时的规则，反推可知：

a. 如果table[i][j] == table[i-1][j]，这说明第$i$件商品没有被选择，则上一步就是在table[i-1][j]的位置处；

b. 如果table[i][j] != table[i-1][j]，说明选择了第$i$件商品，再根据table[i][j] = table[i-1][j-w[i]] + v[i] 可得到上一个位置为table[i-1][j-w[i]]位置处；

c. 如此反复找到 i=0 为止。

示例代码如下：

void show_track()

{

vector<pair<int, int>> track;

int i=N, j=W;

while (i>0) {

if (table[i][j] == table[i-1][j]) {

i--;

} else {

track.push_back(make_pair(i, j));

int w = weight[i];

j -= w;

i--;

}

}

for (int i=0; i<track.size(); i++) {

cout << track[i].first << ' ';

}

}

4. 复杂度分析

根据程序分析可知，我们需要填的表格数量为$N*W$，因此时间复杂度和空间复杂度都是$O(N*W)$，因为要遍历完所有的可能性才可能得到最优解，而不像有序数组一样可以二分法或者什么的，所以时间复杂度没法优化了，但空间复杂度还是可以优化的，因为我们每次更新只与上一时刻状态有关，所以不需要保留这么多时刻的状态，空间复杂度可以优化到$O(W)$，首先分析上一步的核心代码：

for (w=1; w<=W; w++) {

for (k=1; k<=N; k++) {

if (weight[k] > w) {

table[k][w] = table[k-1][w];

} else {

int value1 = table[k-1][w-weight[k]] + value[k];

int value2 = table[k-1][w];

......

}

可以看出，核心代码部分，每次更新仅与上一时刻状态有关，对应到table中就是，每次更新只与table的一个行数据有关，这也就是空间复杂度为什么能够优化为$O(W)$的原因，如果简单的优化成如下代码：

for (w=1; w<=W; w++) {

for (k=1; k<=N; k++) {

if (weight[k] > w) {

table[w] = table[w];

} else {

// 需要 w 前方的 w-weight[k] 处的值

int value1 = table[w-weight[k] + value[k];

int value2 = table[w];

table[w] = ...;

}

上述代码不会得到正确的结果，为什么呢？行扫描我们是从左到右进行的，而我们需要取 $w-weight[k]$，即$w$左边的值，而我们却从左边开始更新的，那么就出现了我们需要的值被开始的更新覆盖了，得到的就是当前时刻的值了，不是期待的上一时刻的值，很显然不可能的得到正确的结果了，为了避免这种覆盖现象发生，我们可以通过反向扫描更新，即从右到左更新，这样更新的位置确定不会被左方的需要，就可以得到正确的结果了，代码如下：

void knapsack_optimization()

{

// 仅使用 table 中第一行

int k, w;

for (k=1; k<=N; k++) {

for (w=W; w>=1; w--) {

if (weight[k] > w) {

table[0][w] = table[0][w];

} else {

int value1 = table[0][w-weight[k]] + value[k];

int value2 = table[0][w];

if (value1 > value2) {

table[0][w] = value1;

} else {

table[0][w] = value2;

}

}

}

}

}

5. 总结

01背包问题解法使用的是二维动态规划进行求解的，朴素二维的动态规划时间复杂度和空间复杂度都是$O(N*W)$，而经过分析代码可以看出，状态转移时，当前时刻状态只与上一时刻的状态有关，所以空间复杂度可以优化到$O(W)$，在优化代码是需要注意的是：需要改变行更新顺序，为了避免新的状态覆盖上一时刻的状态，需要从右到左进行更新状态；有了最优解之后就是回溯最优解，方法步骤遵循上述步骤即可。

附录