Fork me on GitHub

01背包问题

发表于 | 分类于 | | 本文总阅读量 次
01背包问题详解。本文用贪婪法、动态规划法、回溯法和分支定界法四个算法来解决01背包问题（前三种给出了具体实现）。

1. 背包问题

1.1. 问题描述

有$N$件物品和一个最大载重量为$W$的背包（容量不计），其中第$i$件物品的重量为$weights[i]$，价值为$profits[i]$，求解在不超过背包最大载重量的前提下，将哪些物品装入背包可使总价值最大。问题的公式描述是：

$${\max}{\sum}_{i=0}^{N-1}{p_i}{x_i}$$

$$\text{s.t.}\;\;{\sum}_{i=0}^{N-1}{w_i}{x_i}\;\;\;{x_i{\in}{0,1}}$$

其中$p_i$表示第$i$件物品的价值，$w_i$表示第$i$件物品的重量。要求的就是向量$x$。

1.2. 求解策略

01背包的特点是：每种物品仅有一件，可以选择放还是不放。

下述分别用贪婪法、动态规划法、回溯法和分支定界法来给出求解策略。其中贪婪法不能保证一定获得最优解，但是它能非常接近最优解，而且有较好的性能。其它三种算法都能获得最优解。

1.2.1. 贪婪法

01背包有若干种贪婪策略：

  1. 价值贪婪准则：从剩余物品中选出可以装入背包的价值最大的物品。
  2. 重量贪婪准则：从剩余的物品中选出可装入背包的重量最小的物品。
  3. 价值密度$p_i/w_i$贪婪准则：从剩余物品中选出可装入背包的$p_i/w_i$值最大的物品。

通过简单的分析可知，上述三种贪婪策略都不能保证得到最优解。但是价值密度贪婪准则是一个好的启发式算法，在更多时候，它的解非常接近最优解。而且该算法能在$O(nlogn)$时间内完成，这是非常好的性能。

由于三种算法思路简单，易于实现，在此不在贴出代码。

1.2.2. 动态规划法

定义状态：$dp(i,j)$表示将前$i$个物品装入最大载重量为$j$的背包中所能获得的最大价值。

根据状态可分析：当要抉择是否要装入第$i$件物品时，可分两种情况，一种是不装入，则$dp(i,j)=dp(i-1,j)$；另一种是装入，则最大价值为装入前$i-1$件物品能获得的最大价值加上第$i$件物品的价值，即$dp(i,j)=dp(i-1,j-weights(i))+profits(i)$。考虑两种情况中能获得较大价值的那种情况，即为要选择的策略。

所以状态转移方程为：

$$dp(i,j)=\begin{cases} \max{dp(i-1,j), dp(i-1,j-weights(i-1))+profits(i-1)}, & \text{j >= weights(i-1)} \ dp(i-1,j), & \text{0 <= j < weights(i-1)} \end{cases}$$

如果用$x[0:N-1]$表示装入的最佳策略，其中如果装入第$i$件物品x[i]=1，否则x[i]=0。则通过上述分析可知，当$dp(i,W)=dp(i-1,W)$时，没有装入第$i$件物品，否则就应该装入第$i$件物品。

通过上述分析，代码如下（这里假设背包最大载重量、物品重量、价值都是整数）：

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
/*
 * 01背包问题
 */

#include <iostream>
#include <vector>
using namespace std;

/*
 * @param: W: 背包的最大承重量
 * @param: weights: 每件物品的重量
 * @param: profits: 每件物品的价值
 * @parma: x: 容量为N的向量，当x[i]=1表示装入第i件物品，x[i]=0表示不装入该物品
 * @param: return: 返回最大价值
 */
int maxProfit(int W, vector<int>& weights, vector<int>& profits, vector<bool>& x){
    int size = profits.size();
    if (weights.size() != size) return -1;
    vector<vector<int> > dp(size+1, vector<int>(W+1));
    for (int i = 0; i <= size; ++i){
        for (int j = 0; j <= W; ++j){
            if (i == 0) dp[i][j] = 0;
            if (i > 0 && j >= weights[i-1]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+profits[i-1]); 
        }
    }
    for (int i = 1; i <= size; ++i){
        if (dp[i][W] == dp[i-1][W]) x[i-1] = 0;
        else x[i-1] = 1;
    }
    return dp[size][W];
}

int main(int argc, char** argv){
    int arr_weights[] = {5, 4, 3, 2, 1};
    int arr_profits[] = {20, 15, 10, 5, 1};
    vector<int> weights(arr_weights, arr_weights+sizeof(arr_weights)/sizeof(int));      // 每件物品的重量
    vector<int> profits(arr_profits, arr_profits+sizeof(arr_profits)/sizeof(int));      // 每件物品的价值
    int W = 9;                                                                          // 背包总重量
    vector<bool> x(sizeof(arr_weights)/sizeof(int));                                    // 用来存储是否装入第i件物品
    cout << maxProfit(W, weights, profits, x) << endl;                                  // 输出最大价值
    for (int i = 0; i < x.size(); ++i)                                                  // 输出装载策略
        cout << x[i] << ' ';
    cout << endl;
    return 1;
}

代码输出：

1
2
35
1 1 0 0 0

可以发现上述程序时间复杂度为$O(NW)$，空间复杂度为$O(NW)$。其中时间复杂度不能再优化，但是空间复杂度可以再优化。

通过状态转移方程可知，$dp(i,j)$只与$dp(i-1,j)$和$dp(i-1,j-weights(i))$有关。可以只用一个一维向量$f[0:W]$来表示背包最大载重量为$0$到$W$时能获得的最大价值。然后不断更新该向量。比如，当放入前0件物品时，可以得到向量$f[0:W]$的值，当要放入前1件物品时，通过状态转移方程可知它只与放入前0件物品时的$f[0:W]$有关，此时状态转移方程为：$f(j):=\max{f(j),f(j-weights(0))+profits(0)}$。依次类推，可知当要装入前$i$件物品时，状态转移方程为：

$$f(j) := \begin{cases}f(j), & \text{j>=weights(i-1)} \ f(j-weights(i-1))+profits(i-1), & \text{0<=j<weights(i-1)}\end{cases}$$

此时空间复杂度为$O(W)$，不过此时不能获知装入的策略。代码如下：

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
/*
 * 01背包问题
 */

#include <iostream>
#include <vector>
using namespace std;

/*
 * @param: W: 背包的最大承重量
 * @param: weights: 每件物品的重量
 * @param: profits: 每件物品的价值
 * @parma: x: 容量为N的向量，当x[i]=1表示装入第i件物品，x[i]=0表示不装入该物品
 * @param: return: 返回最大价值
 */
int maxProfit(int W, vector<int>& weights, vector<int>& profits){
    int size = profits.size();
    if (weights.size() != size) return -1;
    vector<int> dp(W+1);
    for (int i = 0; i <= size; ++i){
        for (int j = W; j >= 0; --j){
            if (i == 0) dp[j] = 0;
            if (i > 0 && j >= weights[i-1]) dp[j] = max(dp[j], dp[j-weights[i-1]]+profits[i-1]); 
        }
    }
    return dp[W];
}

int main(int argc, char** argv){
    int arr_weights[] = {5, 4, 3, 2, 1};
    int arr_profits[] = {20, 15, 10, 5, 1};
    vector<int> weights(arr_weights, arr_weights+sizeof(arr_weights)/sizeof(int));      // 每件物品的重量
    vector<int> profits(arr_profits, arr_profits+sizeof(arr_profits)/sizeof(int));      // 每件物品的价值
    int W = 9;                                                                          // 背包总重量
    cout << maxProfit(W, weights, profits) << endl;                                  // 输出最大价值
    return 1;
}

代码输出：

1
35

1.2.3. 回溯法

01背包问题是选择一个物品的子集，来装入背包，以便获取最大价值，则解空间就应该组织成子集树结构。然后采用深度优先遍历来探索该子集树。只要左孩子表示一个可行的节点，就沿着左分支移动；否则，当右子树可能含有优于当前最优解的解的时候，搜索右子树。是否要搜索右子树，一个简单的判定方法是，当前节点的收益加上还未考察的对象的收益是否超过当前最优解的收益，如果不是，则不需要搜索右子树。

实现代码如下：

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
/*
 * 01背包问题
 */

#include <iostream>
#include <vector>
using namespace std;

// 全局变量
int N;                      // 物品数量
int W;                      // 背包最大载重量
int remainingWeights;       // 剩余的物品重量
int currentWeights;         // 当前的载重量
int currentProfits;         // 当前装载的价值
int bestProfits;            // 最大装载价值
vector<int> weights;        // 每件物品的重量
vector<int> profits;        // 每件物品的价值
vector<bool> x;             // 当前的策略
vector<bool> bestX;         // 最佳策略

/*
 * @param: i: 第i层
 */
void rKnapsack(int i){
    if (i >= N){             // 回溯结束条件
        if (currentProfits > bestProfits){
            bestProfits = currentProfits;
            bestX = x;
        }
        return;
    }
    remainingWeights -= weights[i];
    if (currentWeights + weights[i] <= W){                  // 搜索左子树
        x[i] = 1;
        currentWeights += weights[i];
        currentProfits += profits[i];
        rKnapsack(i+1);
        currentWeights -= weights[i];
        currentProfits -= profits[i];
    }
    if (currentWeights + remainingWeights > bestProfits){   // 搜索右子树
        x[i] = 0;
        rKnapsack(i+1);
    }
}

int main(int argc, char** argv){
    int arr_weights[] = {5, 4, 3, 2, 1};
    int arr_profits[] = {20, 15, 10, 5, 1};
    N = sizeof(arr_weights)/sizeof(int);
    W = 9;
    remainingWeights = 0;
    currentWeights = 0;
    currentProfits = 0;
    bestProfits = 0;
    weights.assign(arr_weights, arr_weights+N);
    profits.assign(arr_profits, arr_profits+N);
    x = vector<bool>(N);
    bestX = vector<bool>(N);
    for (int i = 0; i < N; ++i)
        remainingWeights += weights[i];

    rKnapsack(0);                   // 开始回溯
    cout << bestProfits << endl;    // 输出最大价值
    for (int i = 0; i < N; ++i)     // 输出选择策略
        cout << bestX[i] << ' ';
    cout << endl;
    return 1;
}

代码输出：

1
2
35
1 1 0 0 0

1.2.4. 分支定界法

分支定界法和回溯法很相似，先将解空间构造为子集树，然后采用广度优先遍历来获取最佳策略。由于分支定界法占用内存大（需要存储将要扩展的节点），效率不高，所以不如回溯法。代码等以后补充。

1.3. 小结

贪婪法是一种启发式算法，虽然不能保证获取最优解，但是能获得近似解，而且效率高，一般价值密度贪婪准则的实用效果更好。动态规划法是一种常用的算法，能获得最优解，而且直观、易于理解。回溯法和分支定界法都是将解空间构建为子集树，然后遍历搜索所有情况，相比于暴力搜索，这两种方法都采用界定函数来缩小搜索的范围（即去掉不必要搜索的节点），由于分支定界法的空间需求比回溯法要大的多，因此当内存容量有限时，回溯法更容易成功。

2. 参考资料

  1. 背包问题九讲