貪心算法解決最優(yōu)裝載問題

輝彩園林綠化工程有限公司網(wǎng)站中期課程設計報告PAGE4PAGE7算法設計與分析實驗報告//author:KevinBlack//這個是我剛剛做好的作業(yè)，我覺得應該上傳一些文檔到豆丁//老師···假如你看到我的作業(yè)跟網(wǎng)上的這個文章一樣···你別以為我是抄的啊···//記得看看作者的名字?。。∝澬乃惴ㄖ顑?yōu)裝載問題一.實驗目的掌握貪心算法的基本思想（具體闡述）掌握貪心算法的基本要素：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)二.實驗內(nèi)容貪心算法基本思想：整體劃分成部分，分而治之。每個部分中尋找最優(yōu)解，然后綜合所有部分最優(yōu)解。這是，可能得到整體的最優(yōu)解，但往往得到的是近似的最優(yōu)解。貪心算法基本要素：1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。2.最優(yōu)子結(jié)構(gòu)性質(zhì)當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)裝載問題1.問題描述：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。2.數(shù)學描述：三.實驗程序及運行結(jié)果#include<iostream.h>#include<stdlib.h>voidSwap(int&x,int&y)//交換{ intt; t=x; x=y; y=t;}voidsort(intw[],intt[],intn)//排序，由小到大{ for(intm=0;m<n;m++)//為每個物品編序號 { t[m]=m; } inti,j; intlastExchangeIndex; i=n-1; while(i>0) { lastExchangeIndex=0; for(j=0;j<i;j++) { if(w[j+1]<w[j]) { Swap(w[j+1],w[j]);//物品重量交換 lastExchangeIndex=j; Swap(t[j],t[j+1]);//物品序號交換 } } i=lastExchangeIndex;//當不存在交換的時候，lastExchangeIndex=0，循環(huán)結(jié)束 }}voidLoading(intx[],intw[],intc,intn,int*t)//傳址{ sort(w,t,n); for(inti=0;i<n;i++)x[i]=0; for(intj=0;j<n&&w[t[j]]<=c;j++) { x[t[j]]=1;//裝入 c-=w[t[j]]; }}intmain(){ intn,c; cout<<"請輸入物品個數(shù)："<<endl; cin>>n; cout<<"請輸入最大容量："<<endl; cin>>c; int*t=newint[n];//存儲物品編號 int*w=newint[n];//存儲每個物品重量 for(inti=0;i<n;i++) { cout<<"請輸入第"<<i<<"個物品重量："<<endl; cin>>w[i]; } int*x=newint[n];//物品是否裝入 for(intj=0;j<n;j++)//初始化所有物品均為不裝入 { x[j]=0; } Loading(x,w,c,n,t); cout<<"裝入物品編號為："<<endl; for(intk=0;k<n;k++) { if(x[k]==1) cout<<t[k]+1<<""; } //釋放數(shù)組資源空間 delete[]t; delete[]w; delete[]x; return0;}四．實驗分析證明：1.最優(yōu)裝在問題具有貪心選擇性質(zhì)：分析：當載重量為定值c時，Wi越小時，可裝載的集裝箱數(shù)量n越大。問題劃分為i個子問題，只要依次選擇最小重量集裝箱，滿足小于等于c。原問題即可由i個子問題的最優(yōu)解得到整體的最優(yōu)解。所以，最優(yōu)裝在問題具有貪心選擇性質(zhì)。y=max(x1w1+x2w2+…+xiwi+…+xnwn)具體的做法：首先排序整個集裝箱（依照重量從小到大的順序），然后盡可能多地選出前i個集裝箱，要求y=(x1w1+x2w2+…+xiwi)<=c.輸出所選集裝箱編號。任務完成。2.最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)：分析：由2中的分析可以看出，一個問題的最優(yōu)解包含其子問題的最優(yōu)解，所以，最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3.由于最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，最優(yōu)裝載問題符合貪心算法。參考文獻[1]/sfzx/jpsykc/xlcad/xu04.html#(18)內(nèi)容總結(jié)

（1）//author:KevinBlack

//這個是我剛剛做好的作業(yè)，我覺得應該上傳一些文檔到豆丁

//老師···假如你看到我的作業(yè)跟網(wǎng)上的這個文章一樣···你別以為我是抄的啊···

//記得看看作者的名字啊