装载问题

装载问题
有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，集装箱总重量小于等于c1+c2,要求定一个合理的装载方案可将这n个集装箱装上这两艘轮船。

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

1）首先将第一艘轮船尽可能装满

2）将剩余的集装箱装上第二艘轮船

 

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和接近第一艘轮船载重量c1.

该问题类似于0-1背包问题，可以用动态规划法解决。

 

用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。

 

回溯法实现：

/*
 * 装载问题
 * 有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船
 * 要求确定一个合理的装载方案可将这n个集装箱装上这两艘轮船。
 * 
 * 解决策略：
 * 1）首先将第一艘轮船尽可能装满
 * 2）将剩余的集装箱装上第二艘轮船
 * 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和接近轮船载重量。
 * 类似于0-1背包问题 可以使用动态规划解决
 * 
 * 回溯法解决：
 * 用子集树表示解空间
 *
 * 
 * date:2010/12/12
 * auther: cm
 */
public class LoadProblem 
{
	private int n;			//集装箱数量
	private double[] w;		//集装箱重量数组
	private double c;		//第一艘轮船的载重量
	private double cw;		//当前载重量
	private double bestw;	//最优载重量

	//用于剪去不含最优解的子树
	private double rw;		//剩余集装箱重量

	//用于构造最优解
	private int[] x;		//当前解
	private int[] bestx;	//当前最优解


	public LoadProblem(double[] w, double c)
	{
		this.w = w;
		this.c = c;
		n = w.length;
		x = new int[n];
		bestx = new int[n];

		for (int i = 0; i < n; i++)
		{
			rw += w[i];
		}
	}

	//计算最优载重量
	public double maxLoading()
	{
		backtrack(0);
		return bestw;
	}

	//回溯算法
	private void backtrack(int i)
	{
		//搜索第i层节点
		if (i >= n)	//到达页节点
		{
			//System.out.println("达到叶节点.............");
			if (cw > bestw)
			{
				//System.out.println("更新bestw...........");
				bestw = cw;
				for (int j = 0; j < x.length; j++)
				{
					bestx[j] = x[j];
				}
			}
			return;
		}

		//搜索子树
		if (cw + w[i] <= c)
		{
			x[i] = 1;
			cw += w[i];
			backtrack(i + 1);
			cw -= w[i];
		}
		

		rw -= w[i];
		//搜索右子树
		if (cw + rw > bestw)	//剪去不含最优解的子树
		{
			x[i] = 0;
			backtrack(i + 1);
		}
		rw += w[i];
	}

	public int[] getBestx()
	{
		return bestx;
	}


	public static void main(String[] args) 
	{
		double[] w = {40, 40, 10};
		double c1 = 50;
		LoadProblem load = new LoadProblem(w, c1);
		System.out.println(load.maxLoading());
		int[] x = load.getBestx();
		for (int i = 0; i < x.length; i++)
		{
			System.out.print(x[i] + " ");
		}
	}
}