Boil's Blog HomeArchivesTagsCategories
分支界限法第一讲
Word count: 2.4k|Reading time: 10 min

分支界限法实现01背包(homework)

题目内容

经典的01背包问题，给定物品个数，背包容量，n个物品的质量和价值，问最大能装多少，这里还要求输出最大的方案

实现思路

这里首先简单介绍一下分支界限法的思路。分支界限法和之前回溯法使用的不同的地方在于：分支界限法是一种广度优先的思想，不是一路走到头，而是利用队列（或优先队列）对各层进行逐一遍历。这样做的一个好处在于我们可以在过程中对总体情况的把握更加清晰。分支界限的意思是我们要在这里把握好界限函数，也就是过程中不能超过总容量，并且也要时刻关注剪枝条件。在这里，我们使用一个优先队列，这个优先队列排序的条件是每个点估计的上界，这个我们需要先对每个点的单位价值大到小排序，这样的话我们之后估计的时候就估计剩下单位价值如果都是这么大，乘上剩下的体积，就是一个上限。如果这个上限比先前得到的最大值还要小，那么这里就剪枝。这里和课本上在实现上有一些不同。我这里为每个节点配置一个布尔类型的vector数组用于记录之前的每个点的取舍情况，以方便最后输出最佳方案的时候使用。这个方法与课本上的方法相比，好处在于可以方便输出方案，不需要回溯，并且不需要再构建子集树我们对用过的节点直接删去，减少了一定的空间复杂度。

实现细节

这里的细节还是有点多。首先要注意每次从队头取点后立刻pop，否则后续加新点后可能替代原来的队头，导致弹出的item错误。然后还要注意临界判断，第一个要push如一个根，level是0，他并不是真正的物体，只是为了之后的统一处理。在子节点的判断时n-1时就要停下来判断

实现代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
//
//  15th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/6/3.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 150
typedef long long ll;
using namespace std;

struct node
{
    double w,v,up;
    int level;
    vector<bool> record;
    bool operator <(const node kk)const
    {
        return up<kk.up;
    }
};

struct item
{
    double w;
    double v;
    double bi;
};

bool cmp(item x, item y)
{
    return x.bi > y.bi;
}

priority_queue<node> q;
int n;
double tot_space;
item a[100010];
double ans,ans_wei;
node ans_node;

void bag()
{
    while(!q.empty())
    {
        node tmp = q.top();
        q.pop();
        if (tmp.level==n-1)
        {
            if (tmp.w+a[n].w<=tot_space && tmp.v+a[n].v > ans)
            {
                ans = tmp.v+a[n].v;
                ans_node = tmp;
                ans_wei = tmp.w + a[n].w;
                ans_node.record.push_back(true);
            }
            else
            {
                if(tmp.v > ans)
                {
                    ans = tmp.v;
                    ans_node = tmp;
                    ans_wei = tmp.w;
                    ans_node.record.push_back(false);
                }
            }
            continue;
        }
        double tmp_wei = tmp.w+a[tmp.level+1].w;
        if(tmp_wei<=tot_space && tmp.v + a[tmp.level+1].v + (tot_space-tmp_wei)*a[tmp.level+2].bi > ans)
        {
            node new_node;
            new_node.w = tmp_wei;
            new_node.v = tmp.v + a[tmp.level+1].v;
            new_node.level = tmp.level +1;
            new_node.up = tmp.v + a[tmp.level+1].v + (tot_space-tmp_wei)*a[tmp.level+2].bi;
            new_node.record = tmp.record;
            new_node.record.push_back(true);
            q.push(new_node);
        }
        if (tmp.v + (tot_space-tmp.w)*a[tmp.level+2].bi > ans)
        {
            node new_node;
            new_node.w = tmp.w;
            new_node.v = tmp.v;
            new_node.level = tmp.level +1;
            new_node.up = tmp.v + (tot_space-tmp.w)*a[tmp.level+2].bi;
            new_node.record = tmp.record;
            new_node.record.push_back(false);
            q.push(new_node);
        }
    }
    cout << "max value and the weight of it:" << endl;
    cout << ans << " " << ans_wei << endl;
    cout << "The items we pick as follows: (weight value)" << endl;
    for (int i=0;i<ans_node.record.size();i++)
        if(ans_node.record[i])
            cout << a[i+1].w << " " << a[i+1].v << endl;
}
/*
 思路简述：
    这里和课本上在实现上有一些不同。我这里为每个节点配置一个布尔类型的vector数组用于记录之前的每个点的取舍情况，以方便
    最后输出最佳方案的时候使用。这个方法与课本上的方法相比，好处在于可以方便输出方案，不需要回溯，并且不需要再构建子集树
    我们对用过的节点直接删去，减少了一定的空间复杂度。
    这里用到的剪枝方法就是先排序，后面每次判断会不会上界小于目前最优
 
 样例输入1：（表示有5件物品，背包总容量1000，第一行是五件东西的质量，第二行是五件东西的价值）
 5 1000
 144 487 210 567 1056
 990 436 673 58 897
 
 样例输入2：（表示有5件物品，背包总容量3，第一行是五件东西的质量，第二行是五件东西的价值）
 5 3
 1 1 1 1 1
 1 2 3 4 5
*/

int main()
{
    cin >> n >> tot_space;
    for (int i=1;i<=n;i++)
        cin >> a[i].w;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i].v;
        a[i].bi = a[i].v/a[i].w;
    }
    sort(a+1, a+n+1, cmp);
    node rot;
    rot.level = 0; rot.v=0; rot.w=0; rot.up = tot_space*a[1].bi;
    q.push(rot);
    ans = 0;
    bag();
}

分支界限法实现旅行售货员问题(homework)

题目内容

旅行售货员问题是个很经典的问题。题目的意思就是一个售货员要经过所有的城市并回到原来的城市，问最短路径长度是多少，并输出方案

实现思路

这里使用分支界限法解决这个题。关于分支界限法的思想见上题，这里应用的思路在于，我们这里对每个节点node结构体中定义路径path，层级level，当前到level层的花费，level+1到n层的花费下界，还有就是我们定义的优先队列排序依据：当前花费加预估的下界。注意，这里node里的路径path包含已确定路径，也就是1–level是已确定的，剩下的是未确定的，每次level+1到时候从未确定区间内取一个加入已确定区间。这样做不仅可以方便最后输出方案，同时也很好避免了搜索到重复点，不需要再另外加机制判断重复点问题。

实现细节

输入的时候注意设置成-1后如果要去重取小注意分类判断

实现代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//
//  16th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/6/9.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 150
typedef long long ll;
using namespace std;

struct node
{
    int level,low,restsum,now; //level表示层数，low表示最优解的下界，restsum表示之后下界和，now是当前长度
    int record[1010]; //用于记录路径，1-level为确定，level+1-n为不确定
    bool operator <(const node kk)const
    {
        return low>kk.low;
    }
};
priority_queue<node> q;
int n,m,ans;
int mp[1010][1010];
int min_cost[1010]; //用于记录每个点相连的最短边，用于每次更新路径总长度的下界
node ans_node;

void travel()
{
    while(!q.empty())
    {
        node tmp = q.top();
        q.pop();
        if (tmp.level == n) //到达最后一个点
        {
            if (mp[tmp.record[n]][1] == -1) //如果不存在边就跳过
                continue;
            if (tmp.now + mp[tmp.record[n]][1] < ans) //小就更新
            {
                ans = tmp.now + mp[tmp.record[n]][1];
                ans_node = tmp;
            }
            continue;
        }
        for (int loc = tmp.level+1;loc <= n;loc++) //遍历level+1开始每个点
        {
            int plen = mp[tmp.record[tmp.level]][tmp.record[loc]]; //表示level点到这个点长度
            if (plen == -1)    //不存在边，跳过
                continue;
            int tmp_low = tmp.now + plen + tmp.restsum - min_cost[tmp.record[loc]]; //表示如果取这个点后的路径下界
            if (tmp_low > ans) //如果路径长度下界比当前最小值大就不取
                continue;
            node newnode; //建立新节点
            newnode.level = tmp.level+1;
            newnode.restsum = tmp.restsum - min_cost[tmp.record[loc]];
            newnode.now = tmp.now + plen;
            newnode.low = newnode.restsum + newnode.now;
            for (int i=1;i<=n;i++)
                newnode.record[i] = tmp.record[i];
            swap(newnode.record[tmp.level+1], newnode.record[loc]);
            q.push(newnode);
        }
    }
    if (ans == INF) //不存在解
    {
        cout << "No solution" << endl;
        return;
    }
    cout << "The lowest cost is: " << endl;
    cout << ans << endl;
    cout << "The path is:" << endl;
    for (int i=1;i<=n;i++)
        cout << ans_node.record[i] << " ";
    cout << 1 << endl;
    return;
}
/*
 测试数据1：
 5 8
 1 2 5
 1 4 7
 1 5 9
 2 3 10
 2 4 3
 2 5 6
 3 4 8
 4 5 4
 测试数据2:
 4 6
 1 2 30
 1 3 6
 1 4 4
 2 4 10
 2 3 5
 3 4 20
 测试数据3：
 3 1
 1 2 10
 */
int main()
{
    cin >> n >> m;
    memset(mp, -1, sizeof(mp));
    memset(min_cost, 0x4f4f4f, sizeof(min_cost));
    int tx,ty,tw;
    ans = INF;
    for (int i=1;i<=m;i++)
    {
        cin >> tx >> ty >> tw;
        if (mp[tx][ty] == -1)
            mp[tx][ty] = tw;
        else
            mp[tx][ty] = min(mp[tx][ty],tw); //重复边直接取最小
        if (mp[ty][tx] == -1)
            mp[ty][tx] = tw;
        else
            mp[ty][tx] = min(mp[ty][tx],tw); //重复边直接取最小
        min_cost[tx] = min(min_cost[tx], tw); //更新每个点相连的最短边长度
        min_cost[ty] = min(min_cost[ty], tw);
    }
    int ini_re = 0; //代表根节点出发期望的下界
    for (int i=1;i<=n;i++)
        ini_re += min_cost[i];
    node rot;
    rot.level = 1; rot.now = 0; rot.restsum = ini_re; rot.low = ini_re;
    for (int i=1;i<=n;i++)
        rot.record[i] = i;
    q.push(rot);
    travel();
    return 0;
}
Author: YihangBao
Link: https://roarboil.github.io/2020/06/03/cha6-1/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.