📑 例题：01背包问题
题目链接：采药-洛谷
当洛谷上不让下载测试用例，可以试试：采药-ACWing
-
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？ -
输入格式
第一行有 22 个整数T
T
T（
1
≤
T
≤
1000
1 \le T \le 1000
1≤T≤1000）和 MM（
1
≤
M
≤
100
1 \le M \le 100
1≤M≤100），用一个空格隔开，
T
T
T代表总共能够用来采药的时间，
M
M
M代表山洞里的草药的数目。
接下来的M
M
M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
-
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
01背包问题很经典，回溯、分支限界、动态规划都可以用来解决它。这里使用的是分支限界法。
注：例题中采药的时间就相当于物品的质量或体积。
🌵 分析：分支限界解法
基本思路
分支限界法类似于广度优先搜索，可使用队列实现，但进行了优化：
- 求出原问题的一个上界和下界。由于背包问题中要求总价值的最大化，则：
上界：大于等于最优解
下界：某个可行解 - 搜索过程中
某结点处的上界1已经低于原问题的下界，则该分支不必继续搜索
某可行解达到了原问题的上界，则该可行解即为原问题的最优解，停止搜索 - 上界和下界可以是 （也可以不是，为了效率罢了） 动态变化的，搜索时将上界和下界不断靠拢，缩小最优解可能存在的范围，那么最后：真相只有一个！
更新上界：（后面“优先队列的使用”将会介绍）
更新下界：如果找到某可行解大于原来的下界，则将它作为原问题的新下界
优先队列的使用
简介
优先队列式分支限界法：每次算完限界后，把搜索树上当前所有叶结点的限界进行比较。找出限界最优的结点，此结点即为下次分支的结点。2
优先队列的一个意义在于，总是搜索当前看起来最优的结点，因此更有可能更快地找到最优解。此外，它可以帮助进行上界的更新。
上界函数与上界的更新
- 原问题上界更新：优先队列中，队首结点的上界作为此时原问题的上界。
- 如何保证队首结点的上界是全局的上界？(不仅是队列中上界最大的结点，而是整个解空间树种上界最大的结点)
- 这将涉及上界函数的选取，它需要有这样的性质：
结
点
上
界
>
=
以
该
节
点
为
根
的
子
树
中
所
有
结
点
的
上
界
结点上界>=以该节点为根的子树中所有结点的上界
结点上界>=以该节点为根的子树中所有结点的上界
（你可能感觉这是理所当然，根结点的上界当然不会比子结点的上界小，但笔者是踩过这个坑的，并为此debug到夜晚两点半）
- 上界函数（ub）
假设所有物品已经按单位价值从大到小排序。- 1）策略：用剩余物品中单价最高的物品填满背包的剩余空间 （可以理解为切下一部分）
结
点
上
界
=
当
前
背
包
中
物
品
总
价
值
+
剩
余
空
间
×
下
一
个
待
选
择
物
品
的
单
位
价
值
结点上界=当前背包中物品总价值+剩余空间\times下一个待选择物品的单位价值
结点上界=当前背包中物品总价值+剩余空间×下一个待选择物品的单位价值
- 2）策略：选剩余物品单价最高的，把能放的物品放进背包，如果碰到某个物品放不下，就按它的单价填满背包的剩余空间。
- 3）一个错误的策略：按单价从高到低遍历剩余物品，能放得下就放进去，然后选最后放下的一个物品的下一个的单价，用来填满背包的剩余空间。
- 1）策略：用剩余物品中单价最高的物品填满背包的剩余空间 （可以理解为切下一部分）
🍖 举个例子
背包容量
C
=
10
C=10
C=10，物品数量
n
=
4
n=4
n=4。
| 物品序号 | 质量 | 价值 | 单位价值 |
|---|---|---|---|
| 1 | 4 | 24 | 6 |
| 2 | 8 | 40 | 5 |
| 3 | 5 | 20 | 4 |
| 4 | 2 | 6 | 3 |
策略1：
上
界
1
=
6
∗
10
=
60
上界_1=6*10=60
上界1=6∗10=60
策略2：
上
界
2
=
24
+
（
10
−
4
）
∗
5
=
54
上界_2=24+（10-4）*5=54
上界2=24+（10−4）∗5=54
策略3：
上
界
3
=
24
+
20
+
(
10
−
4
−
5
)
∗
3
=
47
上界_3=24+20+(10-4-5)*3=47
上界3=24+20+(10−4−5)∗3=47
策略 1 和 2 都是对的，后者更精确一些，使用它的搜索效率也会更高。（你也许无法相信，某个测试用例下，前者搜索了
两
百
多
万
个
两百多万个
两百多万个结点，而后者只搜索了
一
百
多
个
一百多个
一百多个结点，就像差之毫厘，谬以千里）
🍭 搜索树如下图（策略 1）
有问题的策略3
策略 3 求的确实是上界没有问题，而且比策略 2 更精确。问题在于它不满足：
结
点
上
界
>
=
以
该
节
点
为
根
的
子
树
中
所
有
结
点
的
上
界
结点上界>=以该节点为根的子树中所有结点的上界
结点上界>=以该节点为根的子树中所有结点的上界
🍗 示例2
背包容量 C = 10，物品数 n = 6
| 物品序号 | 质量 | 价值 | 单位价值 |
|---|---|---|---|
| 1 | 1 | 10 | 10 |
| 2 | 6 | 55 | 9.17 |
| 3 | 6 | 54 | 9 |
| 4 | 6 | 54 | 9 |
| 5 | 9 | 72 | 8 |
| 6 | 3 | 3 | 1 |
使用策略 1 或 2：
最
优
解
=
82
最优解=82
最优解=82 （正确的最优解）
使用策略 3：
最
优
解
=
68
最优解=68
最优解=68
🍭 搜索树如下图（策略 3）
关于下界
笔者认为，对于当前的背包问题，使用了优先队列后，已经不需要下界了，因为我们总是在选择全局上界最高的结点进行搜索。
实现（C++）
🥣 头文件、结构与函数定义
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
//物品类型
struct thing {
int w;//质量
int v;//价值
double k;//价值比质量（？？需要浮点数吗）
thing() {
w = 1;
v = 0;
}
void getK() {
k = (double)v / w;
}
bool operator<(const thing& s) const {
return k > s.k;
}
};
//搜索树的结点
struct node {
int W;//当前质量
int V;//当前价值
int ub;//该结点上界
int a[105];//部分解
int index;//待决策结点
node() :a{} {
W = 0;
V = 0;
ub = 0;
index = 0;
}
bool operator<(const node& s) const { //用于大根堆（降序优先队列）
return ub < s.ub;
}
void getUb(int C, vector<thing> things, int M) {
int lb = 0;//新放入物品的价值
int _W = W;
int i = index;
//贪心法按价值放能放的物品
while(_W + things[i].w <= C && i < M) {
_W += things[i].w;
lb += things[i].v;
i++;
}
i++;
int leave = (C - _W) * (things[i].k);
ub = V + lb + leave;
}
};
🍚主函数
int main() {
int C = 0;//背包总容量
int M = 0;//物品数目
cin >> C >> M;
vector<thing> things;//物品
priority_queue<node> q;//搜索结点空间
//输入物品，并按单位价值从大到小排序
for (int i = 0; i < M; i++) {
thing t;
cin >> t.w >> t.v;
things.push_back(t);
things[i].getK();
}
sort(things.begin(), things.end());
//开始搜索结点空间
node t;
t.getUb(C, things, M);
q.push(t);
int result = 0;//最优解
while (q.empty() == false) {
node f = q.top();
q.pop();
//得到最优解
if(f.V >= f.ub){
result = f.V;
break;
}
//构造左结点（不选择-0）
if (f.index < M) {
node l = f;
l.index = l.index + 1;
l.getUb(C, things, M);
q.push(l);
}
//构造右结点（选择-1）
if (f.index < M && f.W + things[f.index].w <= C) {
node r = f;
r.W += things[r.index].w;
r.V += things[r.index].v;
r.a[r.index] = 1;
r.index = r.index + 1;
r.getUb(C, things, M);
q.push(r);
}
}
cout << result << endl;
return 0;
}
🧭 bug记录
- bug1：使用不恰当的上界函数
具体的前面已经写到了。 - bug2：物品单位价值使用了int类型
有物品的价值不能被质量整除的情况。 - bug3：c++变量的初始化
我以为thing m();的意思是定义一个变量 m，并调用构造函数进行初始化 （因为有int a(0)这种用法）。编译器是不是理解成了我要定义一个返回值类型为 thing ，名字是 m 的函数？
其实直接thing m;就好了，系统会自己调用构造函数。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/114782.html
