最优装载问题

问题描述：

有一批集装箱要装上一艘载重量为C的轮船，要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

算法分析：

采用重量轻者先装的贪心选择策略，可产生最优装载问题的最优解。

 

算法实现：

OptinalLoading.java

/*
 * 最优装载
 * 有一批集装箱要装上一艘载重量为C的轮船。
 * 要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
 * 算法分析：
 * 采用重量最轻者先装的贪心选择策略
 * 
 * date: 2010/12/12
 * auther:cm
 *
 */
import java.util.Arrays;
public class OptinalLoading 
{
	private double c;	//载重量
	private LContainer[] loadC;	//集装箱数组
	private int count;			//可装入总数

	public OptinalLoading(double c, double[] w)
	{
		this.c = c;
		this.loadC = new LContainer[w.length];
		for (int i = 0; i < w.length; i++)
		{
			loadC[i] = new LContainer(w[i], i);
		}
	}
	public void optinalLoading()
	{
		Arrays.sort(loadC);
		double max = c;
		double sum = 0.0;
		for (int i = 0; i < loadC.length&&loadC[i].getW()<=max; i++)
		{
			loadC[i].setLoadFlag(true);
			count++;
			sum += loadC[i].getW();
			max -= loadC[i].getW();
		}
	}
	public LContainer[] getLoadC()
	{
		return loadC;
	}
	public int getCount()
	{
		return count;
	}


	public static void main(String[] args) 
	{
		double c = 1000;
		double[] w = {800, 1000, 1001, 200, 100, 400, 600, 50};
		OptinalLoading opt = new OptinalLoading(c, w);
		opt.optinalLoading();
		int count = opt.getCount();
		LContainer[] cc = opt.getLoadC();

		System.out.println(count);
		for (int i = 0; i < cc.length; i++)
		{
			if (cc[i].getLoadFlag())
			{
				System.out.print(cc[i].getId() + " ");
			}
		}
	}
}

 

LContainer.java

//集装箱类
public class LContainer implements Comparable
{
	private int id;	//编号
	private double w; //重量
	private boolean loadFlag = false;	//是否装船标识

	public LContainer()
	{
	}
	public LContainer(double w, int id)
	{
		this.id = id;
		this.w = w;
	}


	public int compareTo(Object obj)
	{
		double ww = ((LContainer)obj).getW();
		if (this.w > ww)
		{
			return 1;
		}
		else if (this.w < ww)
		{
			return -1;
		}
		else
		{
			return 0;
		}

	}

	public void setId(int id)
	{
		this.id = id;
	}
	public int getId()
	{
		return id;
	}
	public void setW(double w)
	{
		this.w = w;
	}
	public double getW()
	{
		return w;
	}
	public void setLoadFlag(boolean loadFlag)
	{
		this.loadFlag = loadFlag;
	}
	public boolean getLoadFlag()
	{
		return loadFlag;
	}
}