（2）回溯法

#include
#include
#define num 100
int bestx[num] = { 0 };	//存放最优解
int w[num];	//集装箱重量
int x[num];	//解
int bestw = 0;	//最优装船重量
int cw = 0;	//当前已装船重量
int n;	//集装箱个数
int c1;	//第一船的重量
int c2;	//第二船的重量//限界函数 
int bound(int t)		// 选择当前节点又分支的剩余集装箱重之和
{int rw = 0;for (int i = t + 1; tn)		//到底叶子节点，求得一个可行解{if (cw>bestw){		//当前解比以前解更优 bestw = cw;for (i = 1; i <= n; i++)bestx[i] = x[i];};return;}else{if (cw + w[t]bestw)		//右分支满足限界条件loadingRec(t + 1);}
}
int main(){n = 4;		//集装箱个数printf("集装箱个数:");scanf("%d",&n); printf("集装箱重量:");w[1] = 4, w[2] = 5, w[3] = 3, w[4] = 2;		//集装箱重量for(int i=1;i<=n;i++){scanf("%d",&w[i]);}c1 = 8;		//第一个船重量c2 = 7;		//第二个船重量printf("第一个船重量:");scanf("%d",&c1);printf("第二个船重量:"); scanf("%d",&c2); cw = 0;bestw = 0;loadingRec(1);		//从第一个集装箱开始装箱printf("第一船的最优装载量为：%d\n", bestw);printf("第一船的最优解为");for (int i = 1; i <= n; i++)printf("%d ", bestx[i]);//求剩余集装箱的重量int cw2 = 0;for (int i = 0; i <= n; i++)if (bestx[i] == 0)cw2 += w[i];if (cw2>c2)printf("无法将剩余集装箱转入第二船，问题无解");elseprintf("可以将剩余集装箱装入第二船，问题有解");getchar();
}

（3）分支限界法

#include 
#include 
#include 
#include
#define num 100
float w[num];	//集装箱重量
int x[num];	//解
float c;
int n;	//集装箱个数
float bestw;
using namespace std;
template
class HeapNode; 
template
class bbnode;
template
void AddLiveNode(priority_queue > &H,bbnode  *E,Type wt,bool ch,int lev);
template
Type MaxLoading(Type w[],Type c,int n,int bestx[]);
template
class bbnode
{friend void AddLiveNode(priority_queue  > &H,bbnode  *E,Type wt,bool ch,int lev);friend Type MaxLoading(Type*,Type,int,int*);friend class AdjacencyGraph;//邻接矩阵public:bbnode *parent;//指向父节点的指针bool Lchild;//左儿子结点标志
};
template
class HeapNode
{friend void AddLiveNode(priority_queue > &H,bbnode  *E,Type wt,bool ch,int lev);friend Type MaxLoading(Type *,Type,int,int*);public:operator Type () const{return uweight;}public:bbnode  *ptr;//指向活结点在子集树中相应结点的指针Type uweight;//活结点优先级(上界)int level;//活结点在子集树中所处的层序号
};
//将活结点加入到表示活结点优先队列的最大堆H中
template
void AddLiveNode(priority_queue  > &H,bbnode  *E,Type wt,bool ch,int lev)
{bbnode  *b = new bbnode ;b->parent = E;b->Lchild = ch;HeapNodeN;N.ptr = b;N.uweight = wt;N.level = lev;H.push(N);
}
//优先队列式分支限界法,返回最优载重量,bestx返回最优解
//优先级是当前载重量+剩余重量
template
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{priority_queue > H;//定义最大堆的容量为1000Type *r = new Type [n+1];//剩余重量r[n] = 0;for(int j = n - 1;j > 0;j--){r[j] = r[j+1] + w[j+1];}//初始化int i = 1;//当前扩展结点所在的层bbnode  *E = 0;//当前扩展结点Type Ew = 0;//扩展结点所相应的载重量//搜索子集空间树while(i != n + 1)//非叶子节点{//检查当前扩展结点的儿子节点if(Ew+w[i] <= c){AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);//左儿子结点为可行结点}AddLiveNode(H,E,Ew+r[i],false,i+1);//右儿子结点HeapNodeN =H.top();//取下一扩展结点H.pop();//下一扩展结点,将最大值删去i = N.level;E = N.ptr;Ew = N.uweight - r[i-1];//当前优先级为上一优先级-上一结点重量}//构造当前最优解,类似回溯的过程for(int j = n;j > 0;j--){bestx[j] = E->Lchild;E = E->parent;}return Ew;
}
int main(){printf("轮船重量:");scanf("%f",&c);printf("请输入物品个数：");scanf("%d", &n);printf("物品的重量:");for(int i=1;i<=n;i++){scanf("%f",&w[i]);}bestw=MaxLoading(w,c,n,x);cout<<"分支限界选择结果为："<