贪心法装载问题.doc

方法一：问题描述有n个集装箱要装上1艘载重量分别为c的轮船，其中第i个集装箱的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船，并找出一种装载方案输入输入有若干组测试数据(不超过20组)。每组测试数据有2行：第1行上是集装箱个数n和船的载重量c，（n1000，c65535）；第2行上有n个整数w1、w2、wn，整数之间用一个空格分开，这n个整数依次表示这n个集装箱的重量，（0wi 1000，i=1,2,n）。输出现要求对输入中的每组测试数据，输出3行：在第1行上输出“Case #”，其中“#”是测试数据的组号（从1开始）。在第2行上两个整数bestn、leftc其中bestn是船能装的最多的集装箱数，leftc是对应于bestn的船的最大剩余载重量。在第3行上输出一个0-1字符串x1x2xn，其中x1x2xn是对应于bestn的具体装载方案，xi=1表示第i个集装箱装在船上，而xi=0表示第i个集装箱不装在船上。对应于bestn的装载方案可能不唯一，如重量分别为40、10、40的3个集装箱，若船的载重量是50，那么只能装2个集装箱上船，因此有装载方案110和011两种。为使输出结果唯一，我们约定长为n的0-1字符串以字典序最大的那个为符合要求的装载方案，此例中应为110。输入样例3 5040 10 405 3710 30 24 35 40输出样例Case 12 0110Case 22 310100package greedy;import java.util.Arrays;class Element implements Comparable float weight; int i; public int getI() return i; public void setI(int i) this.i = i; public float getWeight() return weight; public void setWeight(float weight) this.weight = weight; public Element(float weight, int i) super(); this.weight = weight; this.i = i; public int compareTo(Object o) / TODO 自动生成方法存根 float xw=(Element)o).weight; if(weightxw) return -1; if(weight=xw) return 0; return 1;/* author Administrator*/public class OptLoad private Element element;private float c;public OptLoad(Element element,float c) super();this.element = element;this.c=c; public int loading() Arrays.sort(element); int result=0; for(int i=0;ielement.length&elementi.getWeight()=c;i+) result+; c-=elementi.getWeight(); return result; /* * param args */public static void main(String args) / TODO 自动生成方法存根方法二：最优装载问题实现#include iostream.hvoid Sort(int *w,int *t,int n);int main() int n,c; cout请输入所要装载物品的数量n;int *w=new intn+1; /指向物品的重量int *t=new intn+1; /指向物品的序号 cout请输入该单位所能够装载的最大重量：c;cout请输入所要装载的物品的重量endl;for(int i=1;iwi; for(i=1;in+1;i+)ti=i;Sort(w,t,n);for(i=1;i=n&wi=c;i+)/xti=1;c-=wi;cout输出所装载的物品序列号以及它的重量为：ti wiendl;delete w;delete t;return 0;void Sort(int *w,int *t,int n)int temp,tem;for(int j=0;jn+1;j+