最优装载问题_贪心

一、  问题描述

   有一批集装箱要装上一艘载重为C的轮船。其中集装箱i的重量为Wi。最优装载问题要去确定在装载体积不受限制的情况下，将极可能多的集装箱装上轮船。

二、  解题思路及所选算法策略的可行性分析

使用贪心算法。

问题描述为：

    max∑Xi，∑WiXi<=C，Xi∈{0,1}   1<=i<=n

其中，变量Xi=0表示不装入集装箱i，Xi=1表示装入集装箱i。

贪心选择性质：

    设集装箱已依其重量从小到大排序，(X1,X2,…,Xn)是最优装问题的一个最优解。又设k=min{i|Xi=1}。易知，如果给定的最优装载问题有解，则1<i<=n,i!=k,则

    ∑WiYi = Wi - Wk + ∑WiXi <= ∑WiXi <= C

因此，(Yz,Y2,…,Yn)是所给最优装载问题的可行解。

    另一方面，由∑Yi = ∑Xi知，(Y1,Y2,…,Yn)是满足贪心选择性质的最优解。

最优子结构性质：

    设(X1,X2,…,Xn)是最优装载问题的满足贪心选择性质的最优解，则容易知道，X1=1，且（X2,…,Xn）是轮船载重量为C-W1,待装载集装箱为{2,3,…,n}时相应最优集装箱问题的最优解。也及时说，最优集装箱装载问题具有最优子结构性质。

三、  代码描述及复杂度分析

Loading(float c, float[]w, int[] x)

{

   创建集装箱数组，存放每个集装箱重量及其序号；

    按集装箱重量从小到大排序；

    有小到大依次判断是否可入箱；

    返回轮船上箱子总重量；

}

四、代码实现

package 贪心算法;

import 分治法.dcPoint;

class Element implements Comparable{
	float w;
	int i;
	
	public Element(float ww, int ii) {
		w=ww;
		i=ii;
	}
	
	public int compareTo(Object x)
	{
		float xw=((Element)x).w;
		if(w<xw) return -1;
		if(w==xw) return 0;
		return 1;
	}
}

class MergeSort{
	public static void mergeSort(Element[] a){
		Element[] tempArray = new Element[a.length];
		mergeSort(a, tempArray, 0, a.length - 1);
	}
	
	private static void mergeSort(Element[] a, Element [] tempArray, int left, int right){
		if(left < right){
			int center = (left + right) >> 1;
			//分治
			mergeSort(a, tempArray, left, center);
			mergeSort(a, tempArray, center + 1, right);
			//合并
			merge(a, tempArray, left, center + 1, right);
		}
	}
	
	private static void merge(Element [] a, Element [] tempArray, int leftPos, int rightPos, int rightEnd){
		int leftEnd = rightPos - 1;
		int numOfElements = rightEnd - leftPos + 1;
		
		int tmpPos = leftPos;		//游标变量, 另两个游标变量分别是leftPos 和 rightPos
		
		while(leftPos <= leftEnd && rightPos <= rightEnd){
				if(a[leftPos].w <= a[rightPos].w)
					tempArray[tmpPos++] = a[leftPos++];
				else
					tempArray[tmpPos++] = a[rightPos++];
		}
		
		while(leftPos <= leftEnd)
			tempArray[tmpPos++] = a[leftPos++];
		while(rightPos <= rightEnd)
			tempArray[tmpPos++] = a[rightPos++];
		
		//将排好序的段落拷贝到原数组中
		System.arraycopy(tempArray, rightEnd-numOfElements+1, a, rightEnd-numOfElements+1, numOfElements);
	}
}
public class 最优装载{
	public static float loading(float c, float[]w, int[]x)
	{
		int n=w.length;
		Element[]d=new Element[n];
		for(int i=0; i<n; i++)
			d[i]=new Element(w[i],i);
		MergeSort.mergeSort(d);
		float opt=0;
		for(int i=0;i<n;i++)
			x[i]=0;
		for(int i=0;i<n;i++)
		{
			if(w[i]<=c){
				x[d[i].i]=1;
				opt+=d[i].w;
				c-=d[i].w;
			}else
				break;
		}
		return opt;
	}
	
	public static void main(String[] args)
	{
		float weight= (float) 100.00;
		float w[]={1,5,10,14,15,16,20,18,23,32,56,72,85};
		int x[]=new int[w.length];
		
		System.out.println("货物总重量为："+loading(weight, w, x));
		System.out.print("装入集装箱为：");
		for(int i=0; i<w.length; i++)
			if(x[i]==1) 
			System.out.print(i+1+" ");
	}
}

　　

五、代码运行结果截图