seekerhit 2019-11-10
一、 问题描述
有一批集装箱要装上一艘载重为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+" "); } }
五、代码运行结果截图
六、问题总结
常用排序算法还得再好好看看。