说明
本文我先写在我的CSDN上后再转到该博客系统的,有些链接会跳转我的CSDN上
基本思想
类似于回溯法,分支限界法也是一种在问题的解空间树T上搜索问题解的算法。
分支限界法和回溯法
(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解
,或是在满足约束条件的解中找出在某种意义下的最优解
。
(2)搜索方式:回溯法以深度优先的方式
搜索解空间树,而分支限界法则以广度优先或以最大效益优先(最小耗费) 的方式
搜索解空间树。
分支限界法特点
每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点,就一次性产生其所有儿子结点。
- 儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,
其余儿子结点被加入活结点表中
。 - 此后,从活结点表中取
下一结点
成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止
。
常见两种分支限界法
队列式(FIFO)分支限界法
将活结点表组织成一个队列,按照先进先出(FIFO)原则选取下一个结点为扩展结点。
优先队列式分支限界法
将活结点表组织成一个优先队列
,按照规定的优先级,选取优先级最高
的结点成为当前扩展结点。
对于优先队列式分支限界法,在算法实现时,通常用极大(小)堆来实现最大(小)优先队列
,提取堆中下一个结点(堆的根节点)作为当前扩展结点,体现最大(小)费用优先的原则。
极大堆满足一个节点必定不小于其子节点
,极小堆正好相反。
极大堆中最大的元素必定是其根节点
,堆排序算法正式根据这个特性而产生的:对一个序列,将其构造为极大堆,然后将根节点(数组首元素)和数组的尾元素交换,之后对除了尾元素之外的序列继续以上过程,直到排序完成
堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)
装载问题
问题描述
有n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且
问题:
是否有一个合理的装载方案,可将这n个集装箱装上这2艘轮船?如果有,找出一种装载方案。
例如:当n=3, c1=c2=50
(1)若w=[10, 40, 40]
可将集装箱1和集装箱2装上第一艘轮船,而将集装箱3装上第二艘轮船;
(2)如果w=[20, 40, 40]
则无法将这3个集装箱都装上船;
基本思路
已证明,如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。
- 首先将第一艘轮船尽可能装满;
- 将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近c1。由此可知,装载问题等价于以下特殊的0-1背包问题。
队列式分支限界法
- 解装载问题的队列式分支限界法
仅求出所要求的最优值
,稍后进一步构造最优解。 - 首先检测当前扩展结点的左儿子结点是否为可行结点。如果是,则将其加入到活结点队列Q中。
- 然后,将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后,当前扩展结点被舍弃。
- 活结点队列中,队首元素被取出作为当前扩展结点。
- 活结点队列已空,算法终止。
例子
例如 n=4, c1=12, w=[8, 6, 2, 3].
注:叶子结点不会被扩展,因此不用加入到活结点队列当中,此时,只需要检查该叶节点表示的最优解是否优于当前最优解,并实时更新当前最优解。
同层尾部标记:-1
活结点队列:当取出的元素是-1时,判断当前队列是否为空,如果队列不空,则将尾部标记 -1加入到活节点队列中,代表算法开始处理下一层活节点,即:代表算法开始处理 下一个物品的装载问题(每一层i开始处理第i个物品的装载)。
代码(伪代码)
emplate<class Type>
Type MaxLoading(Type w[], Type c, int n)
{ //初始化
Queue<Type>Q; // 活结点队列
Q.Add(-1); // 同层结点尾部标志
int i=1; //当前扩展结点所处的层
Type Ew=0; //扩展结点处相应的载重量
bestw=0;
//搜索子集空间树
while (true) {
// 检查左儿子结点
if (Ew + w[i] <= c1) // x[i] = 1,Ew存储当前扩展结点相应的载重量
EnQueue(Q, Ew + w[i], bestw, i, n); //将活结点加入到活结点队列Q中
// 右儿子结点总是可行的,将其加入到Q中
EnQueue(Q, Ew, bestw, i, n); // x[i] = 0
Q.Delete(Ew); // 取下一扩展结点
if (Ew == -1) { // 同层结点尾部
if (Q.IsEmpty( )) return bestw;
Q.Add(-1); // 同层结点尾部标志
Q.Delete(Ew); // 取下一扩展结点
i++;} // 进入下一层
}
}
算法的改进
算法MaxLoading初始时bestw=0,直到搜索到第一个叶结点才更新bestw。在搜索到第一个
叶结点前,总有Ew+r>bestw, 此时右子树测试不起作用。
为确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值。
样例
分析演示
代码改进(伪代码)
while (true) {
// 检查左儿子结点
// wt=Ew + w[i]; // 左儿子结点的重量
if (wt<= c) { // 可行结点
if (wt > bestw) bestw = wt; //提前更新bestW,注意更新条件
// 加入活结点队列
if (i <= n) Q.Add(wt);
}
// 检查右儿子结点
if (Ew + r > bestw && i <= n) //右儿子剪枝
Q.Add(Ew); // 可能含最优解
Q.Delete(Ew); // 取下一扩展结点
if (Ew == -1) { // 同层结点尾部
if (Q.IsEmpty()) return bestw;
Q.Add(-1); // 同层结点尾部标志
Q.Delete(Ew); // 取下一扩展结点
i++;
r-=w[i];} // 进入下一层
}
}
代码
#include <bits/stdc++.h>
using namespace std;
typedef struct QNode
{
QNode *parent;
int lchild;
int weight;
}QNode;
int n;
int c;
int bestw;
int w[100];
int bestx[100];
void InPut()
{
scanf("%d %d", &n, &c);
for(int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
// for(int i = 1; i <= n; ++i)
// printf("%d ", w[i]);
// cout << endl;
// printf("输入结束\n");
}
//QNode *&bestE 的原因是 首先bestE是个地址, 其次引用为了赋值使用, 后边for循环中用到
void EnQueue(queue<QNode *> &q, int wt, int i, QNode *E, QNode *&bestE, int ch)
{
if(i == n)
{
if(wt == bestw)
{
bestE = E;
bestx[n] = ch;
return;
}
}
QNode *b;
b = new QNode;
b->weight = wt;
b->lchild = ch;
b->parent = E;
q.push(b);
}
int MaxLoading()
{
queue<QNode *>q;
q.push(0);
int i = 1;
int Ew = 0, r = 0;
bestw = 0;
for(int j = 2; j <= n; ++j)
r += w[j];
QNode *E, *bestE; //bestE的作用是:结束while循环后,bestE指向最优解的叶子节点,然后通过bestE->parent找到装入了哪些物品。
E = new QNode; //E这里作为一个中间量,连接parent和child
E = 0; //赋0是因为树的根的值是0,while刚开始的时候其代表root
while(true)
{
int wt = Ew + w[i];
if(wt <= c)
{
if(wt > bestw) //提前更新bestW,注意更新条件
bestw = wt;
EnQueue(q, wt, i, E, bestE, 1);
}
if(Ew + r >= bestw) //右儿子剪枝
{
EnQueue(q, Ew, i, E, bestE, 0);
}
E = q.front();
q.pop();
if(!E) //如果取得的数是0,代表该处理下一层
{
if(q.empty()) //如果队列为空,表示该循环结束了
break;
q.push(0); //如果队列中还有数据,表示循环还没结束。在该层的末尾加一个0标识符
E = q.front();
q.pop();
i++; //下一层走起
r -= w[i]; //计算剩余的重量
}
Ew = E->weight; //不要忘记更新最新节点的值
}
for(int j = n - 1; j > 0; --j)
{
bestx[j] = bestE->lchild;
bestE = bestE->parent;
}
}
void OutPut()
{
printf("最优装载量为 %d\n", bestw);
printf("装载的物品为 \n");
for(int i = 1; i <= n; ++i)
if(bestx[i] == 1)
printf("%d ", i);
}
int main()
{
InPut();
MaxLoading();
OutPut();
}
样例测试
数据为上面那个样例
输入
4 12
8 6 2 3
输出
最优装载量为 11
装载的物品为
1 4
优先队列式分支限界法
- 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。
- 活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量Ew(即:当前扩展结点船的载重量Ew)再加上剩余集装箱的重量r之和(即:将上界Ew+r定义为结点优先级)。
- 优先队列中优先级最大的活结点成为下一个扩展结点。
- 子集树中叶结点所相应的载重量与其优先级(上界值)相同,即:该叶子结点的上界值等于当前叶子结点处船的重量Ew。
- 在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
求最优解
- 在优先队列的每一个活结点中,保存从解空间树的根结点到该活结点的路径,在算法确定了达到最优值的叶结点时,就在该叶结点处同时得到相应的最优解。
- 在算法的搜索进程中,保存当前已构造出的部分解空间树,这样在算法确定了达到最优值的叶结点时,可以在解空间树中从该叶结点开始向根结点回溯,构造出相应的最优解。
样例
分析演示
代码
#include
using namespace std;
class MaxHeapQNode
{
public:
MaxHeapQNode *parent; //父节点
int lchild; //左节点:1; 右节点"0
int weight; //总重量
int lev; //层次
};
struct cmp
{
bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
{
return a->weight < b->weight;
}
};
int n;
int c;
int bestw;
int w[100];
int bestx[100];
void InPut()
{
scanf("%d %d", &n, &c);
for(int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
}
void AddAliveNode(priority_queue, cmp> &q, MaxHeapQNode *E, int wt, int i, int ch)
{
MaxHeapQNode *p = new MaxHeapQNode;
p->parent = E;
p->lchild = ch;
p->weight = wt;
p->lev = i + 1;
q.push(p);
}
void MaxLoading()
{
priority_queue, cmp > q; // 大顶堆
//定义剩余重量数组r
int r[n + 1];
r[n] = 0;
for(int j = n - 1; j > 0; --j)
r[j] = r[j + 1] + w[j + 1];
int i = 1;
MaxHeapQNode *E;
int Ew = 0;
while(i != n + 1)
{
if(Ew + w[i] <= c)
{
AddAliveNode(q, E, Ew + w[i] + r[i], i, 1);
}
AddAliveNode(q, E, Ew + r[i], i, 0);
//取下一节点
E = q.top();
q.pop();
i = E->lev;
Ew = E->weight - r[i - 1];
}
bestw = Ew;
for(int j = n; j > 0; --j)
{
bestx[j] = E->lchild;
E = E->parent;
}
}
void OutPut()
{
printf("最优装载量为 %d\n", bestw);
printf("装载的物品为 \n");
for(int i = 1; i <= n; ++i)
if(bestx[i] == 1)
printf("%d ", i);
}
int main()
{
InPut();
MaxLoading();
OutPut();
}
样例测试
数据为上面那个样例
输入
4 12
8 6 2 3
输出
最优装载量为 11
装载的物品为
1 4
旅行售货员问题
问题描述:
某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。
结果为: 1 3 2 4 1
问题分析
- 解旅行售货员问题的优先队列式分支限界法
用优先队列存储活结点表
。 - 活结点m在优先队列中的
优先级定义
为:活结点m对应的子树费用下界lcost
。 - lcost=cc+rcost,其中,cc为当前结点费用,rcost为
当前顶点最小出边费用加上剩余所有顶点的最小出边费用和
。 - 优先队列中
优先级最大的活结点
成为下一个扩展结点。 - 排列树中叶结点所相应的载重量与其优先级(下界值)相同,即:
叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值
。 - 与子集树的讨论相似,实现对排列树搜索的
优先队列式分支限界法
也可以有两种不同的实现方式:(旅行售货员问题采用第一种实现方式
。)- 用优先队列来存储活结点。优先队列中
每个活结点都存储从根到该活结点的相应路径
。 - 用优先队列来存储活结点,并同时存储
当前已构造出的部分排列树
。优先队列中的活结点不必存储从根到该活结点的相应路径,该路径必要时从存储的部分排列树中获得
。
- 用优先队列来存储活结点。优先队列中
令Minout[i]代表顶点i的最小出边费用。图中:
Minout[1]=4 Minout[2]=5
Minout[3]=5 Minout[4]=4
如,在扩展顶点D处:
rcost=
Minout[3]+Minout[2]+Minout[4]=14
其中:Minout[3]:当前顶点最小出边
Minout[2],Minout[4]:剩余所有顶点最小出边
算法描述
- 要找最小费用旅行售货员回路,选用
最小堆
表示活结点优先队列。 - 算法开始时创建一个最小堆,用于表示活结点优先队列。
- 堆中每个结点的优先级是
子树费用的下界lcost值
。 - 计算
每个顶点i的最小出边费用
并用minout[i]记录 - 如果所给的
有向图
中某个顶点没有出边
,则该图不可能有回路,算法结束。
基于优先队列式分支限界的旅行售货员问题求解算法
,采用限界函数lcost ,作为优先级
,不断调整搜索方向,选择最有可能取得最优解的子树优先搜索
;同时,根据限界函数lcost进行剪枝,剪掉不包含最优解的分支
。
算法的
while循环完成对排列树内部结点的扩展
。对于当前扩展结点,算法分两种情况
进行处理。令s表示结点在排列树中的层次(节点B为第0层)。考虑排列树层次
s=n-2
的情形,此时当前扩展结点是排列树中某个叶结点的父结点
。
(1).检测图G是否存在一条从顶点x[n-2]
到顶点x[n-1]
的边和一条从顶点x[n-1]
到顶点1的边。
(2). 如果这两条边都存在,则找到一条旅行员售货回路。
(3).此时,算法还需要判断这条回路的费用是否优于
已找到的当前最优回路的费用bestc。
(4). 如果是,则必须更新当前最优值bestc和当前最优解bestx
。if(cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1] < bestc ) { // 找到更优的旅行路径 for (int j = 0; j <= n-1; j++) bestx[j] = x[j]; bestc = cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1]; }
令x记录当前解,s表示结点在排列树中的层次(结点B为第0层)。当扩展结点所处的层次
s<n-2
时,算法依次产生当前扩展结点的所有儿子结点。
(1). 由于当前扩展结点所相应的路径是x[0: s],该扩展结点可行儿子结点
是从剩余顶点x[s+1: n-1]中选取的顶点x[i],且(x[s],x[i])是所给有向图G中的一条边。
(2).对于当前扩展结点的每一个可行儿子结点
,计算出其前缀(x[0:s],x[i])的费用cc和相应的下界lcost。
(3).当lcost<bestc时,将这个可行儿子结点插入到活结点优先队列中,否则,将剪去以该儿子结点为根的子树。
while循环的终止条件:
排列树的一个叶结点成为当前扩展结点, 算法结束
。当s=n-1时,已找到的回路是x[0: n-1],它已包含图G的所有n个顶点。
因此,当s=n-1时,相应的
扩展结点表示一个叶结点
。该叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值
。因为一旦一个叶结点成为当前扩展结点,剩余活结点的下界值(lcost值),都大于等于
当前叶子节点处已找到的回路的费用。它们都不可能导致费用更小的回路。因此,已找到叶结点所相应的回路,是一个最小费用旅行售货员回路,算法结束。
算法结束时,返回找到的最小费用,相应的最优解由数组v给出
优先队列式分支限界法求解TSP问题
s代表当前节点在排列树中层次,从排列树的根节点到当前结点的路径为x[0:s],进一步搜索的顶点为x[s+1: n-1]
class MinHeapNode {
Friend Traveling <Type>;
Public:
Operator Type () const { return lcost;}
private:
Type lcost, 费用下界
Type cc, 当前费用
Type rcost, 顶点最小出边费用和(顶点为:x[s:n-1])
int s, 当前结点在排列树中的层次;
Int *x, 存储解(结点路径)
}
下界:lcost=cc+rcost
Minout[i]:顶点i的最小费用出边
初始化时:cc=0, s=0, x[0]=1, x[1: n-1]=(2,3,…, n)
初始化时:bestc为较大数值
样例
分析演示
代码
#include <iostream>
#define NO_PATH -1 //没有通路
#define MAX_WEIGHT 4000
using namespace std;
int N; //城市数目
int City_Graph[100][100]; //保存图信息
int x[100]; //x[i]保存第i步遍历的城市
int isIn[100]; //保存 城市i是否已经加入路径
int bestw; //最优路径总权值
int cw; //当前路径总权值
int bestx[100]; //最优路径
//-----------------------------------------------------------------
void Travel_Backtrack(int t){ //递归法
int i,j;
if(t>N){ //走完了,输出结果
for(i=1;i<=N;i++) //输出当前的路径
cout<<x[i];
cout<<endl;
if(cw < bestw){ //判断当前路径是否是更优解
for (i=1;i<=N;i++){
bestx[i] = x[i];
}
bestw = cw+City_Graph[x[N]][1];
}
return;
}
else{
for(j=1;j<=N;j++){ //找到第t步能走的城市
if(City_Graph[x[t-1]][j] != NO_PATH && !isIn[j]){ //能到而且没有加入到路径中
isIn[j] = 1;
x[t] = j;
cw += City_Graph[x[t-1]][j];
Travel_Backtrack(t+1);
isIn[j] = 0;
x[t] = 0;
cw -= City_Graph[x[t-1]][j];
}
}
}
}
int main(){
int i;
cout<<"请输入城市数目:";
cin>>N;
for(int i=1;i<=N;i++){
cout<<"请输入第"<<i<<"座城市的路程信息(不通请输入-1):";
for(int j=1;j<=N;j++){
cin>>City_Graph[i][j];
}
}
//测试递归法
for (i=1;i<=N;i++){
x[i] = 0; //表示第i步还没有解
bestx[i] = 0; //还没有最优解
isIn[i] = 0; //表示第i个城市还没有加入到路径中
}
x[1] = 1; //第一步 走城市1
isIn[1] = 1; //第一个城市 加入路径
bestw = MAX_WEIGHT;
cw = 0;
Travel_Backtrack(2); //从第二步开始选择城市
cout<<"最优值为:"<<bestw;
cout<<"最优解为:";
for(i=1;i<=N;i++){
cout<<bestx[i];
}
cout<<endl;
}
测试样例
数据与例子中的数据相同。
输入:
4
-1 30 6 4
30 -1 5 10
6 5 -1 20
4 10 20 -1
输出
1234
1243
1324
1342
1423
1432
最优值为:25最优解为:1423
0-1背包问题
问题描述
- 给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为c。
- 应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
- 在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。
算法的思想
- 首先,要对输入数据进行预处理,将各物品依其
单位重量价值从大到小进行排列。
- 在实现时,由Bound计算当前结点处的上界。在解空间树的当前扩展结点处,
仅当要进入右子树时才计算右子树的上界Bound
,以判断是否将右子树剪。进入左子树时不需要计算上界
,因为其上界与其父节点上界相同。 - 在优先队列分支限界法中,结点的优先级定义为:
以结点的价值上界作为优先级(由bound函数计算出)
步骤
- 算法首先根据基于可行结点相应的
子树最大价值上界优先级
,从堆中选择一个节点(根节点)作为当前可扩展结点。 - 检查当前扩展结点的左儿子结点的可行性。
- 如果左儿子结点是可行结点,则将它加入到子集树和活结点优先队列中。
- 当前扩展结点的右儿子结点一定是可行结点,
仅当右儿子结点满足上界函数约束时,才将它加入子集树和活结点优先队列。
- 当扩展到叶节点时,算法结束,叶子节点对应的解即为问题的最优值。
样例
假设有4个物品,其重量分别为(4, 7, 5, 3),价值分别为(40, 42, 25, 12),背包容量W=10。将给定物品按单位重量价值从大到小排序,结果如下:
物品 | 重量(w) | 价值(v) | 价值/重量(v/w) |
---|---|---|---|
1 | 4 | 40 | 10 |
2 | 7 | 42 | 6 |
3 | 5 | 25 | 5 |
4 | 3 | 12 | 4 |
上界计算
先装入物品1,剩余的背包容量为6,只能装入物品2的6/7(即 42*(6/7)=36
)。 即上界为40+6*6=76
已第一个up为例:40+6*(10-4)=76
打x的部分因为up值已经小于等于bestp了,所以没必要继续递归了。
分析演示
核心代码
- Typew c: 背包容量
- C: 背包容量
- Typew *w: 物品重量数组
- Typew *p: 物品价值数组
- Typew cw:当前重量
- Typew cp:当前价值
- Typep bestcp:当前最优价值
上界函数
template<class Typew, class Typep>
Typep Knap<Typew, Typep>::Bound(int i)
{// 计算上界
Typew cleft = c - cw; // 剩余容量
Typep b = cp;
// 以剩余物品单位重量价值递减序装入物品
while (i <= n && w[i] <= cleft) {
cleft -= w[i];
b += p[i];
i++;
}
// 装满背包
if (i <= n) b += p[i]/w[i] * cleft;
return b;
}
0-1背包问题优先队列分支限界搜索算法
完整代码
#include <bits/stdc++.h>
using namespace std;
class Object
{
public:
int id;
int weight;
int price;
float d;
};
class MaxHeapQNode
{
public:
MaxHeapQNode *parent;
int lchild;
int upprofit;
int profit;
int weight;
int lev;
};
struct cmp
{
bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
{
return a->upprofit < b->upprofit;
}
};
bool compare(const Object &a, const Object &b)
{
return a.d >= b.d;
}
int n;
int c;
int cw;
int cp;
int bestp;
Object obj[100];
int bestx[100];
void InPut()
{
scanf("%d %d", &n, &c);
for(int i = 1; i <= n; ++i)
{
scanf("%d %d", &obj[i].price, &obj[i].weight);
obj[i].id = i;
obj[i].d = 1.0 * obj[i].price / obj[i].weight;
}
sort(obj + 1, obj + n + 1, compare);
// for(int i = 1; i <= n; ++i)
// cout << obj[i].d << " ";
// cout << endl << "InPut Complete" << endl;
}
int Bound(int i)
{
int tmp_cleft = c - cw;
int tmp_cp = cp;
while(tmp_cleft >= obj[i].weight && i <= n)
{
tmp_cleft -= obj[i].weight;
tmp_cp += obj[i].price;
i++;
}
if(i <= n)
{
tmp_cp += tmp_cleft * obj[i].d;
}
return tmp_cp;
}
void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E, int up, int wt, int curp, int i, int ch)
{
MaxHeapQNode *p = new MaxHeapQNode;
p->parent = E;
p->lchild = ch;
p->weight = wt;
p->upprofit = up;
p->profit = curp;
p->lev = i + 1;
q.push(p);
// cout << "加入点的信息为 " << endl;
// cout << "p->lev = " << p->lev << " p->upprofit = " << p->upprofit << " p->weight = " << p->weight << " p->profit = " << p->profit << endl;
}
void MaxKnapsack()
{
priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
MaxHeapQNode *E = NULL;
cw = cp = bestp = 0;
int i = 1;
int up = Bound(1); //Bound(i)函数计算的是i还未处理时候的上限值
while(i != n + 1)
{
int wt = cw + obj[i].weight;
if(wt <= c)
{
if(bestp < cp + obj[i].price)
bestp = cp + obj[i].price;
AddAliveNode(q, E, up, cw + obj[i].weight, cp + obj[i].price, i, 1);
}
up = Bound(i + 1); //注意这里 up != up - obj[i].price而且 up >= up - obj[i].price
if(up >= bestp) //注意这里必须是大于等于
{
AddAliveNode(q, E, up, cw, cp, i, 0);
}
E = q.top();
q.pop();
cw = E->weight;
cp = E->profit;
up = E->upprofit;
i = E->lev;
}
for(int j = n; j > 0; --j)
{
bestx[obj[E->lev - 1].id] = E->lchild;
E = E->parent;
}
}
void OutPut()
{
printf("最优装入量为 %d\n", bestp);
printf("装入的物品为 \n");
for(int i = 1; i <= n; ++i)
if(bestx[i] == 1)
printf("%d ", i);
}
int main()
{
InPut();
MaxKnapsack();
OutPut();
}
测试样例
输入
4 10
40 4
42 7
25 5
12 3
输出
最优装入量为 65
装入的物品为
1 3