算法分析與設(shè)計(jì)貪心算法求解背包問題

1、用貪心算法求解背包問題D軟件101 薛思雨 511020825一、貪心算法介紹顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。貪心算法求解的問題一般具有兩個(gè)重要性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)解的選擇，即貪心選擇

2、來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。二、貪心法的基本思路從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問題：1. 不能保證求得的最后解是最佳的；2. 不能用來求最大或最小解問題；3. 只能求滿足某些約束條件的可行解的范圍。三、關(guān)于貪心算法在背包問題中的應(yīng)用的探討問題描述：0-1背包問題：給定n種物品和一個(gè)背包。物品i的重量是Wi

3、，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包(1)或不裝入背包(0)。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1in。貪心算法解決背包問題有幾種策略：(i) 一種貪婪準(zhǔn)則為：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=

4、2, w=100,10,10, p =20,15,15, c = 105。當(dāng)利用價(jià)值貪婪準(zhǔn)則時(shí)，獲得的解為x= 1 , 0 , 0 ，這種方案的總價(jià)值為2 0。而最優(yōu)解為 0 , 1 , 1 ，其總價(jià)值為3 0。(ii) 另一種方案是重量貪婪準(zhǔn)則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n= 2 ,w=10,20, p=5,100, c= 2 5。當(dāng)利用重量貪婪策略時(shí)，獲得的解為x =1,0, 比最優(yōu)解 0 , 1 要差。(iii) 還有一種貪婪準(zhǔn)則，就是我們教材上提到的，認(rèn)為，每一項(xiàng)計(jì)算yi=vi/si,

5、即該項(xiàng)值和大小的比，再按比值的降序來排序，從第一項(xiàng)開始裝背包，然后是第二項(xiàng)，依次類推，盡可能的多放，直到裝滿背包。有的參考資料也稱為價(jià)值密度pi/wi貪婪算法。這種策略也不能保證得到最優(yōu)解。利用此策略試解n= 3 ,w=20,15,15, p=40,25,25, c=30 時(shí)的最優(yōu)解。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一個(gè)直覺上近似的解。而且這是解決普通背包問題的最優(yōu)解，因?yàn)樵谶x擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1in。貪心算法解決背包問題的算法實(shí)現(xiàn)：#include "iostream" using

6、namespace std; struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品該放的數(shù)量 int flag; /物品編號(hào) ;/物品信息結(jié)構(gòu)體 void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;j<=n;j+) goods0=goodsj; i=j-1; while (goods0.p>goodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(goodinfo g

7、oods,float M,int n) float cu; int i,j; for(i=1;i<=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;i<n;i+) if(goodsi.w>cu)/當(dāng)該物品重量大與剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/確定背包新的剩余容量 if(i<=n) goodsi.X=cu/goodsi.w;/該物品所要放的量 /按物品編號(hào)做降序排列 for(j=2;j<=n;j+) goods0=goodsj; i=j-1; while (goods0.flag&

8、lt;goodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout<<"最優(yōu)解為:"<<endl; for(i=1;i<=n;i+) cout<<"第"<<i<<"件物品要放:" cout<<goodsi.X<<endl; int main(void) cout<<"|-運(yùn)用貪心法解背包問題-|"<<endl; cout<<"|-|

9、"<<endl; int i,j,n; float M; goodinfo *goods; /定義一個(gè)指針 cout<<"press <1> to run the program"<<endl; cout<<"press <0> to exit"<<endl; cin>>j; while(j) cout<<"請(qǐng)輸入物品的總數(shù)量：" cin>>n; goods=new struct goodinfo n+1;

10、 cout<<"請(qǐng)輸入背包的最大容量：" cin>>M; cout<<endl; for(i=1;i<=n;i+) goodsi.flag=i; cout<<"請(qǐng)輸入第"<<i<<"件物品的重量:" cin>>goodsi.w; cout<<"請(qǐng)輸入第"<<i<<"件物品的效益:" cin>>goodsi.p; goodsi.p=goodsi.p/goodsi.w; /得出物品的效益，重量比 cout<<endl; Insertionsort(goods,n); bag(goods,M,n); cout<<"press <1> to run agian"<<endl; cout<<"press <0> to exit"<<endl; cin>>j; syst