分支限界法思想和案例

说明

 本文我先写在我的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个集装箱都装上船；

基本思路

已证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。

1. 首先将第一艘轮船尽可能装满；
2. 将剩余的集装箱装上第二艘轮船。

  将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近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的值。
• 与子集树的讨论相似，实现对排列树搜索的优先队列式分支限界法也可以有两种不同的实现方式：(旅行售货员问题采用第一种实现方式。)
  1. 用优先队列来存储活结点。优先队列中每个活结点都存储从根到该活结点的相应路径。
  2. 用优先队列来存储活结点，并同时存储当前已构造出的部分排列树。优先队列中的活结点不必存储从根到该活结点的相应路径，该路径必要时从存储的部分排列树中获得。

令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循环完成对排列树内部结点的扩展。对于当前扩展结点，算法分两种情况进行处理。

  1. 令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];    
     }

     

  2. 令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函数计算出）

步骤

1. 算法首先根据基于可行结点相应的子树最大价值上界优先级，从堆中选择一个节点（根节点）作为当前可扩展结点。
2. 检查当前扩展结点的左儿子结点的可行性。
3. 如果左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。
4. 当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界函数约束时,才将它加入子集树和活结点优先队列。
5. 当扩展到叶节点时，算法结束，叶子节点对应的解即为问题的最优值。

样例

 假设有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