算法设计与分析回溯算法之装载问题

回溯算法之装载问题

问题描述

给定n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。集装箱装载问题要求确定在不超过轮船载重量的前提下，将尽可能多的集装箱装上轮船（贪心算法中的装载问题讨论的是装载件数；本题讨论的是最大装载重量。）
由于集装箱问题是从n个集装箱里选择一部分集装箱，假设解向量为X(x1, x2, …, xn)，其中xi∈{0, 1}， xi =1表示集装箱i装上轮船， xi =0表示集装箱i不装上轮船。
输入
每组测试数据：第1行有2个整数c和n。C是轮船的载重量（0＜c＜30000），n是集装箱的个数（n≤20）。第2行有n个整数w1, w2, …, wn，分别表示n个集装箱的重量。
输出
对每个测试例，输出两行：第1行是装载到轮船的最大载重量，第2行是集装箱的编号。

输入样例
34 3
21 10 5
输出（考虑最大装载量的最优解）
31（重量）
1 2

考虑最大装载件数的最优解
2（件）
5 10

算法分析

该问题的形式化描述为：

用回溯法解装载问题时，其解空间是一棵子集树，与0 - 1背包问题的解空间树相同。

可行性约束函数可剪去不满足约束条件的子树：

令cw(t)表示从根结点到第t层结点为止装入轮船的重量，即部分解(x1, x2 , …, xt)的重量：

当cw(t)>c时，表示该子树中所有结点都不满足约束条件，可将该子树剪去。

代码

#include <iostream>
using namespace std;
class goods{
	int weight;
public:
	goods(int w=0):weight(w)
	{}
	int get_w(){
		return weight;
	}
	void set(int w){
		weight=w;
	}
	
};

//goods *g,集装箱列表
 //int *best,待求解的最优装载方案
 //int t,子集树数的层号。根节点在第0层，叶节点在第n层
 //int n,集装箱的总数
//int &cw, 当前的轮船的荷载
//int bestcw ,当前的最大荷载
//int *x,满足当前最大荷载的装载方案
//int r剩余的集装箱重量和
void load(goods *g, int *x, int t, int n,int cw, int &bestcw ,int *best,int r,int c){
	if(t>n) {     //已经遍历的到叶子结点，得到了一个解决方案
	    if(cw>bestcw)	{
		for(int i=0;i<n;i++)
	       	    best[i]=x[i];
		    bestcw=cw;
		}
	}	
   else{ //每个结点可以有两个分支，分别利用约束规则和限界规则进行剪枝
	r=r-g[t].get_w();//剩余未处理的物品的重量和，与是否选取当前物品无关
	if(cw+g[t].get_w()<=c){ //  根据题意中的约束条件进行剪枝
	  	x[t]=1;
		cw=cw+g[t].get_w(); //当前装入的物品的重量和
		load(g,x,t+1,n,cw,bestcw,best,r,c);
		cw=cw-g[t].get_w(); //回溯的需要
	}
	if(cw+r>bestcw) {    //限界规则
		x[t]=0;
		load(g,x,t+1,n,cw,bestcw,best,r,c);
	}
	r=r+g[t].get_w(); //回溯的需要
      }
   }
int main(){
	int n,c,bestcw=0;
	int *x,*best, r=0;
	cout<<“请输入物品的件数和轮船的装载重量：";
	cin>>n>>c;
	goods *g;
	g=new goods[n];
	x=new int [n];
	best=new int[n];
	cout<<"请输入每件物品的重量：";
	for(int i=0;i<n;i++)	{
		int w;	cin>>w;  g[i].set(w);r=r+w;
	}
	load(g,x,0,n,0,bestcw,best,r,c);
	cout<<bestcw<<endl;
	for(i=0;i<n;i++)
		cout<<best[i]<<"  ";
	cout<<endl;
	return 0;
}