貪心法裝載問題

《貪心法裝載問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、方法一：問題描述有n個(gè)集裝箱要裝上1艘載重量分別為c的輪船，其中第i個(gè)集裝箱的重量為wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船，并找出一種裝載方案輸入輸入有若干組測試數(shù)據(jù)(不超過20組)。每組測試數(shù)據(jù)有2行：第1行上是集裝箱個(gè)數(shù)n和船的載重量c，（n<1000，c<65535）；第2行上有n個(gè)整數(shù)w1、w2、…、wn，整數(shù)之間用一個(gè)空格分開，這n個(gè)整數(shù)依次表示這n個(gè)集裝箱的重量，（0

2、整數(shù)bestn、leftc其中bestn是船能裝的最多的集裝箱數(shù)，leftc是對應(yīng)于bestn的船的最大剩余載重量。在第3行上輸出一個(gè)0-1字符串x1x2…xn，其中x1x2…xn是對應(yīng)于bestn的具體裝載方案，xi=1表示第i個(gè)集裝箱裝在船上，而xi=0表示第i個(gè)集裝箱不裝在船上。對應(yīng)于bestn的裝載方案可能不唯一，如重量分別為40、10、40的3個(gè)集裝箱，若船的載重量是50，那么只能裝2個(gè)集裝箱上船，因此有裝載方案110和011兩種。為使輸出結(jié)果唯一，我們約定長為n的0-1字符串以字典序最大的那個(gè)為符合要求的裝載方案，此例中應(yīng)為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自動生成方法存根?}}方法二：最優(yōu)裝載問題實(shí)現(xiàn)#include"iostream.h"voidSort(int*w,int*t,intn);intmain(){intn,c;cout<<"請輸入所要裝載物品的數(shù)量"<>n;int*w=newint[n+1