贪心法装载问题.docVIP

方法一： 问题描述 有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字符串x1x2…xn，其中x1x2…xn是对应于bestn的具体装载方案，xi=1表示第i个集装箱装在船上，而xi=0表示第i个集装箱不装在船上。 对应于bestn的装载方案可能不唯一，如重量分别为40、10、40的3个集装箱，若船的载重量是50，那么只能装2个集装箱上船，因此有装载方案110和011两种。为使输出结果唯一，我们约定长为n的0-1字符串以字典序最大的那个为符合要求的装载方案，此例中应为110。 输入样例 3 50 40 10 40 5 37 10 30 24 35 40 输出样例 Case 1 2 0 110 Case 2 2 3 10100 package 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.lengthelement[i].getWeight()=c;i++)??? ?{??? ??result++;??? ??c-=element[i].getWeight();??? ?}??? ?return result;??? } ?/**? * @p