贪心法装载问题

《贪心法装载问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、方法一：问题描述有n个集装箱要装上1艘载重量分别为c的轮船，其中第i个集装箱的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船，并找出一种装载方案输入输入有若干组测试数据(不超过20组)。每组测试数据有2行：第1行上是集装箱个数n和船的载重量c，（n<1000，c<65535）；第2行上有n个整数w1、w2、…、wn，整数之间用一个空格分开，这n个整数依次表示这n个集装箱的重量，（0

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。输入样例35040104053710302

3、43540输出样例Case120110Case22310100packagegreedy;importjava.util.Arrays;classElementimplementsComparable{                floatweight;                inti;                publicintgetI(){                           returni;                }       publicvoidsetI(inti){                         this.i=i;

4、                }      publicfloatgetWeight(){                         returnweight;                }    publicvoidsetWeight(floatweight){                       this.weight=weight;            } publicElement(floatweight,inti){                 super();                this.weight=weight;          

5、      this.i=i;          } publicintcompareTo(Objecto){             //TODO自动生成方法存根            floatxw=((Element)o).weight;           if(weight

6、ment[]element; privatefloatc; publicOptLoad(Element[]element,floatc){  super();  this.element=element;  this.c=c; }   publicintloading()   {    Arrays.sort(element);    intresult=0;    for(inti=0;i

7、  }    returnresult;   } /** *@paramargs */ publicstaticvoidmain(String[]args){  //TODO自动生成方法存根 }}方法二：最优装载问题实现#include"iostream.h"voidSort(int*w,int*t,intn);intmain(){intn,c;cout<<"请输入所要装载物品的数量"<>n;int*w=newint[n+1