0-1背包问题（回溯法）

140 阅读 0 评论 93 点赞

我是靠谱客的博主清秀往事，这篇文章主要介绍0-1背包问题（回溯法），现在分享给大家，希望可以做个参考。

题目描述

一个旅行者有一个背包容积为m的背包，现在有 n 件物品，它们的重量分别是W1，W2，…,Wn,它们的价值分别为V1，V2，…，Vn，求旅行者能获得最大总价值。

算法分析

用回溯法解0-1背包问题，算法步骤如下：

确定问题的解空间，本题是为了从n个物品的集合中找出总价值最大且满足约束条件的一组物品选择方案。对于第i个物品，有且仅有两种选择，即放入背包或者不放入背包，用0和1表示。所以解空间为子集树，共有 $2^n$ 个解。
确定剪枝函数，将不满足约束条件和限界条件的解给去掉

约束条件： $Sigma_{i=1} ^ n w_i x_i$ <= m

限界条件：对于 $x_i$ 而言，前i-1个物品选择的价值已经确定，如果 $x_{i+1}, x_{i+2}, ... , x_{n})$ 的总价值小于等于当前的最大价值减去前i-1个物品产生的价值，就说明当前的搜索路径不可能产生最优解，可以直接剪枝。
从根节点出发，以深度优先搜索的方式遍历整个解空间。

C++代码如下

复制代码

#include <iostream>
#include <vector>
#include <utility>

using std::cin;
using std::cout;
using std::endl;
using ivec = std::vector<int>;
using pair = std::pair<int, int>;
using pvec = std::vector<pair>;

int n;                              //  物品种类数
int capacity;                       //  背包容积
int maximum_val = 0;                //  最大价值

bool satisfy_bound(int flag, int before_sum, pvec &list) {
    int rest_sum = 0;
    for (int i = flag; i <= n; ++i) rest_sum += list[i].first;
    // cout << ((rest_sum > (maximum_val - before_sum)) ? true : false) << endl;
    return (rest_sum > (maximum_val - before_sum)) ? true : false;
}

void backtrack(int i, int weight, int sum, pvec &list, ivec &is_selected) {
    if (i > n) {        
        //  i > n，说明已经搜索到了叶子结点，此时得到了一个可行解，判断该解是否比当前最大值要大
        maximum_val = (maximum_val < sum) ? sum : maximum_val;
    } else {
        if (satisfy_bound(i, sum, list)) {  //  判断是否满足限界条件
            if (weight >= list[i].second) { //  判断是否满足约束条件
                is_selected[i] = 1;
                sum += list[i].first;
                backtrack(i + 1, weight - list[i].second, sum, list, is_selected);
                is_selected[i] = 0;
                sum -= list[i].first;
                backtrack(i + 1, weight, sum, list, is_selected);
            } else {                        //  剪枝
                backtrack(i + 1, weight, sum, list, is_selected);
            }
        }
    }
}

int main() {
    cin >> n >> capacity;
    auto list = pvec(n+1);              //  存放每一种物品，first为价值、second为重量
    auto is_selected = ivec(n+1, 0);    //  记录每一个物品是否被选中，选中为1，未中为0
    for (int i = 1; i <= n; ++i) cin >> list[i].first >> list[i].second;
    backtrack(1, capacity, 0, list, is_selected);
    cout << "最优解为：" << maximum_val << endl;
    return 0;
}

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
#include <iostream>
#include <vector>
#include <utility>

using std::cin;
using std::cout;
using std::endl;
using ivec = std::vector<int>;
using pair = std::pair<int, int>;
using pvec = std::vector<pair>;


int n;                              //  物品种类数
int capacity;                       //  背包容积
int maximum_val = 0;                //  最大价值


bool satisfy_bound(int flag, int before_sum, pvec &list) {
    int rest_sum = 0;
    for (int i = flag; i <= n; ++i) rest_sum += list[i].first;
    // cout << ((rest_sum > (maximum_val - before_sum)) ? true : false) << endl;
    return (rest_sum > (maximum_val - before_sum)) ? true : false;
}

void backtrack(int i, int weight, int sum, pvec &list, ivec &is_selected) {
    if (i > n) {        
        //  i > n，说明已经搜索到了叶子结点，此时得到了一个可行解，判断该解是否比当前最大值要大
        maximum_val = (maximum_val < sum) ? sum : maximum_val;
    } else {
        if (satisfy_bound(i, sum, list)) {  //  判断是否满足限界条件
            if (weight >= list[i].second) { //  判断是否满足约束条件
                is_selected[i] = 1;
                sum += list[i].first;
                backtrack(i + 1, weight - list[i].second, sum, list, is_selected);
                is_selected[i] = 0;
                sum -= list[i].first;
                backtrack(i + 1, weight, sum, list, is_selected);
            } else {                        //  剪枝
                backtrack(i + 1, weight, sum, list, is_selected);
            }
        }
    }
}

int main() {
    cin >> n >> capacity;
    auto list = pvec(n+1);              //  存放每一种物品，first为价值、second为重量
    auto is_selected = ivec(n+1, 0);    //  记录每一个物品是否被选中，选中为1，未中为0
    for (int i = 1; i <= n; ++i) cin >> list[i].first >> list[i].second;
    backtrack(1, capacity, 0, list, is_selected);
    cout << "最优解为：" << maximum_val << endl;
    return 0;
}