";
        cout << v[1];
    }
}

/*****************************************************************
* 类描述：最小堆（队列中元素类型）
* 参数描述：
    x，用于记录当前解；
    s，表示节点在排列树中的层次，从排列树的根节点到该节点的路径为x[0:s]，
        需要进一步搜索的顶点是x[s+1:n-1]。
    cc，表示当前费用，
    lcost，是子树费用的下界，
    rcost，是x[x:n-1]中顶点最小出边费用和。
*****************************************************************/
class MinHeapNode
{
public:
    char name; // 节点的序号
    int rcost, // x[s:n-1]中顶点最小出边费用和
        lcost, // 子树费用的下界
        cc;    // 当前费用
    int s,     // 根节点到当前节点的路径为x[0:s]
        *x;    // 需要进一步搜索的顶点是x[s+1:n-1]

    // 构造节点并递增序号
    MinHeapNode()
    {
        num += 1;
        name = num + 'A';
    }

    // 最小堆中使用下界排序
    bool operator<(const MinHeapNode &MH) const
    {
        return lcost > MH.lcost;
    }

    // 打印节点信息
    void printNode(priority_queue pq)
    {
        cout << "============== Node: " << name << " ==============" << endl;
        cout << "最小出边和(rcost)：" << rcost << "\t子树费用的下界(lcost)：" << lcost 
        << "\t当前费用(cc)：" << cc << "  \t节点所在层(s)：" << s << endl;
        cout << "当前解是(x)：";
        for (int i = 0; i < n - 1; ++i)
            cout << x[i] << "-";
        cout << x[n - 1] << endl;
        // 输出优先级队列
        if (!pq.empty())
        {
            cout << "-- 当前优先队列：";
            for (int i = 0; i < pq.size(); ++i)
            {
                cout << pq.top().name << "(" << pq.top().lcost << ")-";
                pq.pop();
            }
            cout << pq.top().name << "(" << pq.top().lcost << ")" << endl;
        }
        else
        {
            cout << "(优先级队列为空)" << endl;
        }
        cout << "-- 当前最优值（bestC）：" << bestC << endl;
    }
};
/*****************************************************************
* 算法描述：核心算法
        算法开始时创建一个最小堆，表示活节点优先队列。堆中每个节点的lcost
    值是优先队列的优先级。接着计算出图中每个顶点的最小费用出边并用Minout记录。
    如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。
    如果每个顶点都有出边，则根据计算出的Minout作算法初始化。
*****************************************************************/
int BBTSP()
{
    priority_queue pq; // 优先级队列
    MinHeapNode E;                  // 最小堆节点

    int cc, rcost, MinSum, *MinOut, b;
    int i, j;

    MinSum = 0;              // 最小出边费用和
    MinOut = new int[n + 1]; // 计算 MinOut[i] = 顶点i的最小出边费用
    for (i = 1; i <= n; i++)
    {
        MinOut[i] = NoEdge; // 所有的出边初始化为无连接
        // 遍历找出 MinOut[i] = 顶点i的最小出边费用
        for (j = 1; j <= n; j++)
            if (adjMatrix[i][j] != NoEdge && (adjMatrix[i][j] < MinOut[i] || MinOut[i] == NoEdge))
                MinOut[i] = adjMatrix[i][j];
        // 不存在与这个顶点相连接的边
        if (MinOut[i] == NoEdge)
            return NoEdge;
        MinSum += MinOut[i];
    }

    // 初始化最小堆
    E.s = 0;          // 根节点到当前节点的路径为x[0:s]
    E.cc = 0;         // 当前费用为0
    E.rcost = MinSum; // x[s:n-1]中顶点最小出边费用和
    E.x = new int[n]; // 需要进一步搜索的顶点是x[s+1:n-1]
    // 初始化为顺序搜索
    for (i = 0; i < n; i++)
        E.x[i] = i + 1;
    bestC = NoEdge; // 初始化最优值为 NoEdge

    E.printNode(pq);
    //搜索排列空间树
    while (E.s < n - 1) //非叶节点
    {
        if (E.s == n - 2) // 当前扩展节点是叶节点的父节点，判断构成的回路是否最优
        {
            if (adjMatrix[E.x[n - 2]][E.x[n - 1]] != NoEdge && adjMatrix[E.x[n - 1]][1] != NoEdge &&
                (E.cc + adjMatrix[E.x[n - 2]][E.x[n - 1]] + adjMatrix[E.x[n - 1]][1] < bestC || bestC == NoEdge))
            { // 如果更优，则更新费用更小的路
                cout << "\n||||||||||||||||||||| 到达叶子节点的父节点 ———— 并更新最优解 |||||||||||||||||||||"
                     << endl;
                E.printNode(pq);
                bestC = E.cc + adjMatrix[E.x[n - 2]][E.x[n - 1]] + adjMatrix[E.x[n - 1]][1];
                E.cc = bestC;
                E.lcost = bestC;
                E.s++;
                pq.push(E);
            }
            else
            {
                cout << "\n||||||||||||||||||||||| 到达叶子节点的父节点 ———— 不更新 |||||||||||||||||||||||"
                     << endl;
                E.printNode(pq);
                delete[] E.x; // 舍弃需要进一步搜索的节点
            }
        }
        else // 产生当前扩展节点儿子节点
        {
            cout << "\n*************** 开始一个新节点扩展 ***************\n"
                 << endl;
            for (i = E.s + 1; i < n; i++)
            { // 广度优先搜索，进行子节点的扩展
                MinHeapNode N;
                if (adjMatrix[E.x[E.s]][E.x[i]] != NoEdge)   // E.x[E.s] 是当前要扩展的父节点，E.x[i] 是被遍历的子节点
                {                                            // 可行儿子节点
                    cc = E.cc + adjMatrix[E.x[E.s]][E.x[i]]; // 当前费用 = 之前费用 + 新增费用
                    rcost = E.rcost - MinOut[E.x[E.s]];      // 更新最小出边费用和
                    b = cc + rcost;                          // 下界（限界函数）
                    if (b < bestC || bestC == NoEdge)        // 子树可能含最优解 节点插入最小堆
                    {
                        N.s = E.s + 1; // 进入下一层
                        N.cc = cc;
                        N.lcost = b;
                        N.rcost = rcost;
                        N.x = new int[n];
                        for (j = 0; j < n; j++)
                            N.x[j] = E.x[j];
                        // 获得新的路径【换位】
                        N.x[E.s + 1] = E.x[i];
                        N.x[i] = E.x[E.s + 1];
                        pq.push(N); // 加入优先队列
                        N.printNode(pq);
                    }
                }
            }
            delete[] E.x; //完成节点扩展
        }
        if (pq.empty()) // 堆已空
            break;
        E = pq.top(); // 取下一扩展节点
        pq.pop();
    }

    if (bestC == NoEdge) // 无回路
        return NoEdge;
    for (i = 0; i < n; i++) // 将最优解复制到v[1:n]
        v[i + 1] = E.x[i];
    while (pq.size()) // 释放最小堆中所有节点
    {
        E = pq.top();
        pq.pop();
        delete[] E.x;
    }
    return bestC;
}

int main()
{
    input();
    int res = BBTSP();
    printTravel(res);
}
 

问题描述：
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包最大承载重量为C。物品是不可分割的，应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
要求：
随机生成物品和背包数据，利用分支限界法求解该问题并形成解题报告。

一、问题分析：

0-1背包问题用优先队列式分支限界法实现时，
①问题有2^n种可能解（物品放入/不放入背包）；
解空间树为子集树：左子节点（当前物品放入）、右子节点（当前物品不放入）
②约束条件：背包剩余容量 lw ≥ 当前物品重量 w (判断能否生成左孩子结点)
约束剪枝：问题不满足问题约束时停止该分支的搜索
限界条件：当前背包中物品的价值 + 剩余物品装满背包剩余容量的最大价值 （价值上界lv）≥ 之前计算得到的最大价值 bestv （判断能否生成右孩子结点）
限界剪枝：若价值上界＜当前搜索的最优解，则从中间节点继续向子孙节点搜索不可能得到一个比当前更优的可行解，不必继续搜索
③优先队列是用最大堆来存储活节点表，活结点的优先级由当前价值+ 剩余物品至能把背包装满的最大价值（假设物品可分割时），装物品先捡着单位重量价值高的装。优先队列式分支限界法是利用存储解空间树的活结点，并且每次弹出一个作为扩展结点，是一种广度优先搜索遍历。

二、问题的解决方案

①首先，对要输入的数据进行预处理，将各自物品依其单位重量价值进行从大到小排列。
②再进行广度优先搜索，由CalInf函数计算当前节点处的价值上界，在解空间树的当前扩展结点处，仅当进入右子树时才计算右子树的价值上界CalInf，以判断是否将右子树剪枝。（进入左子树不需要计算，因为其上界与其父节点上界相同）
③结点的优先级定义为：以结点的价值上界作为优先级（由CalInf函数计算出）

三、问题求解中遇到的问题

优先队列式分支限界法如何求解价值上界
这里的背包问题，物品只能装或者不装，定义上界函数时，假设背包可以装一部分，即当背包装不下一整件物品时我们只装一部分，所以我们定义的上界函数是当前重量+剩余物品中单位重量价值最大的物品的平均价值*剩余容量。

四、优先队列式分支限界法关键技术

运用广度优先搜索遍历找到最优解
优先队列式分支限界法每次在活结点表中选择一个最大价值的节点进行拓展。
从根结点（按单位价值降序排序后第一个物品）开始，以广度优先的方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。一次性生成所有孩子结点，由于子集树中约定左分支上的值为“1”，因此沿着扩展结点的左分支扩展，则代表装入物品；由于子集树中约定右分支上的值为“0”，因此沿着扩展结点的右分支扩展，则代表不装入物品。此时，判断是否满足约束条件和限界条件，如果满足，则将其加入队列中；反之，舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时为止。
算法流程图：

五、伪代码

定义结点和物品结构体


定义排序优先级：

定义队列的优先级：

计算结点上界：

搜索函数：

效果截图

完整代码如下：

```cpp
//加载头文件 
#include<iostream>//cin cout
#include<queue>//队列 
#include<cstring>//字符串处理 
#include<algorithm>//提供许多泛型算法和函数sort 
#include<stdlib.h>
#include<time.h>
//特殊定义 
using namespace std;// 用到输入输出的时候就可以省略std::不用每次都写 
const int maxn=10;//常变量maxn 最多物品数 


//定义结构体 
struct object//物品结构体
{
    double w;//物品重量
    double v;//物品价值
    double d;//物品单位重量的价值（价值重量比）
    int id;//物品序号
} a[maxn];

int n,W;//物品种数，背包容量
int bestx[maxn];//最优解 
int bestv;//最优总价值

//预处理重排 
bool tmp1(object b1,object b2)//物品优先级，以单位价值高的优先
{
    return b1.d>b2.d;
}

int init()//初始化
{
    memset(bestx,0,sizeof(bestx));//初始化最优解bestx数组，全为0 
    bestv=0;//最优总价值 
    sort(a+1,a+n+1,tmp1);//数组的降序排序 (按单位价值排序) +1:在数组中先从1位置开始存储 
   	for(int i=1;i<=n;i++)
    	printf("a[%d]=%f ",i,a[i].d);
    printf("\n");
    return 0;
   
}
struct node//结点结构体
{
    double cv,lv;//当前价值，价值上界（注意类型）
    int lw;//剩余容量
    int id;//物品排序后的序号
    int x[maxn];//解向量
    node()
    {
        memset(x,0,sizeof(x));//初始化解向量组x 全为0 
        lv=0;//价值上界定义为0 
    }
    node(int cvv,int lvv,int lww,int idd)//构造函数
    {
        memset(x,0,sizeof(x));
        cv=cvv;//当前价值 
        lv=lvv;//价值上界 
        lw=lww;//背包剩余容量 
        id=idd;//物品排序后的序号 
    }
};

struct tmp2//结点优先级，价值上界高的优先级高
{
    bool operator() (node& n1,node& n2)
    {
        return n1.lv<n2.lv;
    }
};
double CalInf(node t)//计算价值上界：当前背包中物品的价值 + 剩余物品装满背包剩余容量的最大价值 
{
    int num=t.id;//获取此节点序号 
    double maxvalue=t.cv;//获取此节点当前价值 
    int left=t.lw;//获取背包剩余容量 
    while(num<=n&&left>=a[num].w)//循环每一个物品 满足条件：剩余容量大于等于此节点物品重量 
    {
        left-=a[num].w;//更新剩余容量 (-此节点物品重量)
        maxvalue+=a[num].v;//更新当前价值 
        ++num;//更新到下一节点 
    }
    if(num<=n&&left>0)//一定要加下标限制  背包剩余容量大于0 
        maxvalue+=1.0*a[num].v/a[num].w*left;
	//最大价值 = 当前重量+剩余物品中单位重量价值最大的物品的平均价值*剩余容量
    return maxvalue;
}

void bfs()
{
    priority_queue<node,vector<node>,tmp2> q;//结构体类型的优先队列 
    int sumv=0;
    int i;
    for(i=1; i<=n; ++i)
            sumv+=a[i].v;//价值上界sumv为所有物品价值之和 
    q.push(node(0,sumv,W,1));//堆内部放入根结点node(当前价值0，价值上界0，背包剩余容量W，物品排序后的序号1) 

    while(!q.empty())
    {
        node live,lchild,rchild;
        live=q.top();//将指针置于堆顶部  获取顶部元素 
        q.pop();//从堆中取出数据 弹出顶部元素 
        int t=live.id;//当前处理物品的序号
        if(t>n||live.lw==0)//到达叶子结点或者没有剩余容量了
        {
            if(live.cv>=bestv)//更新最优解,不加等号的话，第一次计算得到的值不会更新
            {//当前价值大于等于最优总价值 
                for(int i=1; i<=n; ++i)
                    bestx[i]=live.x[i];//最优解=解向量 
                bestv=live.cv;
            }
            continue;
        }
        if(live.lv<bestv)//不满足限界条件 价值上界小于当前价值(即最优总价值) ，不再拓展 
            continue;//限界剪枝：当问题已经搜索到一个可行解时，将其与当前求解状态进行比较，不满足限界条件进行剪枝 

        if(live.lw>=a[t].w)//满足约束条件，背包剩余容量大于等于物品重量，可以放入背包，可以生成左孩子
        {
            lchild.cv=live.cv+a[t].v;//左孩子结点当前价值 = 当前价值+物品价值 
            lchild.lw=live.lw-a[t].w;//左孩子结点剩余容量 =  背包剩余容量-物品重量 
            lchild.id=t+1;//左孩子结点物品排序后的序号=下一物品序号 
            lchild.lv=CalInf(lchild);//左孩子价值上界
            for(int i=1; i<=n; ++i)
                lchild.x[i]=live.x[i];
            lchild.x[t]=1;
            if(lchild.cv>bestv)//注意要更新最优值
                bestv=lchild.cv;//最优价值更新为左孩子当前价值 
            q.push(lchild);
        }

        rchild.cv=live.cv;//右孩子当前价值=当前处理物品价值 
        rchild.lw=live.lw;//右孩子剩余容量 
        rchild.id=t+1;//右孩子序号+1 
        rchild.lv=CalInf(rchild);//右孩子价值上界 
        if(rchild.lv>=bestv)//(判断价值上界)满足限界条件，不放入背包，可以生成右孩子
        {
            for(int i=1; i<=n; ++i)
                rchild.x[i]=live.x[i];
            rchild.x[t]=0;
            q.push(rchild);//加入右节点 
        }
    }
}
void output()
{
    cout<<"可装载物品的最大价值为："<<bestv<<endl;
    cout<<"装入的物品为：";
    for(int i=1; i<=n; ++i)
        if(bestx[i])
            cout<<a[i].id<<" ";
    cout<<endl;
    return ;
}

int main()
{
    cout<<"请输入物品个数：";
    cin>>n;
    cout<<"请输入背包容量：";
    cin>>W;
    /*cout<<"请依次输入物品的重量和价值：";*/
    
    
    
	srand((unsigned)time(NULL));
    for(int i=1;i<=n;++i)//随机生成价值和重量
	{
		a[i].v=rand()%n+1;
		a[i].w=rand()%n+1;
  		cout<<"物品";
		cout<<i;
		cout<<"重量";
		cout<<a[i].w;
		cout<<"价值";
		cout<<a[i].v<<endl; 
    	a[i].d=a[i].v/a[i].w;//物品单位价值 
        a[i].id=i;//物品序号 
        cout<<"单位价值";
        cout<<a[i].d<<endl;
        
	}
    
    /*for(int i=1; i<=n; ++i)
    {
        cin>>a[i].w>>a[i].v;
        a[i].d=a[i].v/a[i].w;
        a[i].id=i;
    }*/
   	init();
    bfs();
    output();
    return 0;
}

问题描述

 有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且
          

$$\sum _{i=1}^n{w}_i\le c_1+c_2$$

问题:
 是否有一个合理的装载方案,可将这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 <bits/stdc++.h>
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<MaxHeapQNode *, vector<MaxHeapQNode *>, 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<MaxHeapQNode *, vector<MaxHeapQNode *>, 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