最優(yōu)裝載問(wèn)題實(shí)驗(yàn)報(bào)告

1、最優(yōu)裝載問(wèn)題的貪心算法實(shí)現(xiàn) 姓名：（學(xué)號(hào)：）一、作業(yè)及實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)本實(shí)驗(yàn)使學(xué)生掌握貪心算法基本要素、步驟及其應(yīng)用二、作業(yè)及實(shí)驗(yàn)原理本實(shí)驗(yàn)是應(yīng)用貪心算法用Java編程語(yǔ)言對(duì)給定輪船的載重量和一批集裝箱，在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。最優(yōu)裝載問(wèn)題的貪心算法見(jiàn)1 的p91-92，Java編程語(yǔ)言見(jiàn)2。三、 作業(yè)及實(shí)驗(yàn)內(nèi)容1. 計(jì)算問(wèn)題及描述: 問(wèn)題描述：給定輪船的載重量c，第n個(gè)集裝箱及其重量wn，將盡可能多得集裝箱裝上輪船。設(shè)第i個(gè)集裝箱為，最多可放數(shù)量n個(gè)。問(wèn)題形式為:2. 算法設(shè)計(jì)及描述：驗(yàn)證問(wèn)題是否符合貪心算法：(1)該問(wèn)題具備貪心選擇性質(zhì):c為定值時(shí)，越小時(shí)，可裝

2、載的集裝箱數(shù)量n越大。問(wèn)題劃分為m個(gè)子問(wèn)題，只要依次選擇最小重量集裝箱，滿足小于等于c。原問(wèn)題即可由n個(gè)子問(wèn)題的最優(yōu)解得到整體的最優(yōu)解。則最優(yōu)裝在問(wèn)題具有貪心選擇性質(zhì)。先排序整個(gè)集裝箱，然后盡可能多地選出前n個(gè)集裝箱，要求輸出所選集裝箱編號(hào)。(2) 該問(wèn)題具備最優(yōu)子結(jié)構(gòu)性質(zhì):一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解，所以，最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。(3) 由于最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，最優(yōu)裝載問(wèn)題符合貪心算法。3. 算法分析：給出具體的算法復(fù)雜度算法運(yùn)行時(shí)間的漸近表示排序的時(shí)間復(fù)雜度為， for循環(huán)的時(shí)間復(fù)雜度為；所以空間復(fù)雜度為O(m)。4. 程序設(shè)計(jì):根據(jù)所設(shè)計(jì)的算法,

3、寫出完整的算法Java程序或 其他語(yǔ)言程序,并給出相應(yīng)的程序運(yùn)行結(jié)果算法的程序?qū)崿F(xiàn)：#includestdafx.hvoid outputResult(int *r,int len) printf(結(jié)果：); for(int i=0;i0;i-) for(int j=0;jboxj+1) int temp=boaj; boxj=boxj+1; boxj+1=temp; void loading(int *box,int *r,int w,int n) r0=1; w=box0; for(int i=1;i=0) w-=boxi; ri=1; int_tmain(int argc,_TCHAR*argv) int w=100; int box6=100,20,25,25,20,20; sortBox(box,6); int result6=0; loading(box,result,w,6); outputResult(result,6); getchar(); return 0;5. 實(shí)驗(yàn)總結(jié)：寫出本次作業(yè)及實(shí)驗(yàn)心得通過(guò)本次實(shí)驗(yàn)，我們加深領(lǐng)會(huì)了貪心算法的中心思想，實(shí)驗(yàn)過(guò)程中，需要運(yùn)用了最優(yōu)子結(jié)構(gòu)性質(zhì)，貪心選擇性質(zhì)等等，通過(guò)對(duì)這些知識(shí)點(diǎn)得運(yùn)用，我們更加深層次的了解貪心算法的精髓。參考文獻(xiàn)1 王曉東編.