📑 例题：01背包问题
题目链接：采药-洛谷
当洛谷上不让下载测试用例，可以试试：采药-ACWing
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 22 个整数 T TT（1 ≤ T ≤ 1000 1 \le T \le 10001≤T≤1000）和 MM（1 ≤ M ≤ 100 1 \le M \le 1001≤M≤100），用一个空格隔开，T TT代表总共能够用来采药的时间，M MM代表山洞里的草药的数目。
接下来的 M MM 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
01背包问题很经典，回溯、分支限界、动态规划都可以用来解决它。这里使用的是分支限界法。
注：例题中采药的时间就相当于物品的质量或体积。
🌵 分析：分支限界解法
基本思路
分支限界法类似于广度优先搜索，可使用队列实现，但进行了优化：
求出原问题的一个上界和下界。由于背包问题中要求总价值的最大化，则：
上界：大于等于最优解
下界：某个可行解
搜索过程中
某结点处的上界1已经低于原问题的下界，则该分支不必继续搜索
某可行解达到了原问题的上界，则该可行解即为原问题的最优解，停止搜索
上界和下界可以是 （也可以不是，为了效率罢了） 动态变化的，搜索时将上界和下界不断靠拢，缩小最优解可能存在的范围，那么最后：真相只有一个！
更新上界：（后面“优先队列的使用”将会介绍）
更新下界：如果找到某可行解大于原来的下界，则将它作为原问题的新下界
优先队列的使用
简介
优先队列式分支限界法：每次算完限界后，把搜索树上当前所有叶结点的限界进行比较。找出限界最优的结点，此结点即为下次分支的结点。2
优先队列的一个意义在于，总是搜索当前看起来最优的结点，因此更有可能更快地找到最优解。此外，它可以帮助进行上界的更新。
上界函数与上界的更新
- 原问题上界更新：优先队列中，队首结点的上界作为此时原问题的上界。
如何保证队首结点的上界是全局的上界？(不仅是队列中上界最大的结点，而是整个解空间树种上界最大的结点)
这将涉及上界函数的选取，它需要有这样的性质：结 点 上 界 > = 以 该 节 点 为 根 的 子 树 中 所 有 结 点 的 上 界 结点上界>=以该节点为根的子树中所有结点的上界结点上界>=以该节点为根的子树中所有结点的上界
（你可能感觉这是理所当然，根结点的上界当然不会比子结点的上界小，但笔者是踩过这个坑的，并为此debug到夜晚两点半）
上界函数（ub）
假设所有物品已经按单位价值从大到小排序。
1）策略：用剩余物品中单价最高的物品填满背包的剩余空间 （可以理解为切下一部分）
结 点 上 界 = 当 前 背 包 中 物 品 总 价 值 + 剩 余 空 间 × 下 一 个 待 选 择 物 品 的 单 位 价 值 结点上界=当前背包中物品总价值+剩余空间\times下一个待选择物品的单位价值结点上界=当前背包中物品总价值+剩余空间×下一个待选择物品的单位价值
2）策略：选剩余物品单价最高的，把能放的物品放进背包，如果碰到某个物品放不下，就按它的单价填满背包的剩余空间。
3）一个错误的策略：按单价从高到低遍历剩余物品，能放得下就放进去，然后选最后放下的一个物品的下一个的单价，用来填满背包的剩余空间。
🍖 举个例子
背包容量C = 10 ，物品数量n = 4 。
| 物品序号 | 质量 | 价值 | 单位价值 |
| 1 | 4 | 24 | 6 |
| 2 | 8 | 40 | 5 |
| 3 | 5 | 20 | 4 |
| 4 | 2 | 6 | 3 |
策略1:上界_1=6*10=60
策略2:上界_2=24+（10-4）*5=54
策略3:上界_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 （正确的最优解）
使用策略 3：最 优 解 = 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;就好了，系统会自己调用构造函数。
