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

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

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

3、 背包問題：給定 n 種物品和一個背包。物品 i 的重量是 Wi ，其價值為 Vi ，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？在選擇裝入背包的物品時， 對每種物品 i 只有 2 種選擇，即裝入背包 (1)或不裝入背包 (0)。不能將物品 i 裝入背包 多次，也不能只裝入部分的物品 i。背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，K i < n。 貪心算法解決背包問題有幾種策略：(i) 一種貪婪準(zhǔn)則為：從剩余的物品中，選出可以裝入背包的價值最大的物品，利用這種規(guī)則，價值最大的物品首先被裝

4、入(假設(shè)有足夠容量) ，然后是下一個價值最大的物品，如此 繼續(xù)下去。 這種策略不能保證得到最優(yōu)解。 例如， 考慮 n=2, w=100,10,10, p =20,15,15, c = 105。當(dāng)利用價值貪婪準(zhǔn)則時，獲得的解為x= 1 , 0 , 0 ，這種方案的總價值為 2 0。而最優(yōu)解為 0 , 1 , 1 ，其總價值為 3 0。(ii) 另一種方案是重量貪婪準(zhǔn)則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖 然這種規(guī)則對于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n= 2 ,w=10,20, p=5,100, c= 2 5 。當(dāng)利用重量貪婪策略時， 獲得的解為

5、x =1,0, 比最優(yōu)解 0 , 1要差。(iii) 還有一種貪婪準(zhǔn)則，就是我們教材上提到的，認(rèn)為，每一項計算yi=vi/si, 即該項值和大小的比，再按比值的降序來排序，從第一項開始裝背包，然后是第二項，依次類推，盡可能 的多放，直到裝滿背包。有的參考資料也稱為價值密度 pi/wi 貪婪算法。這種策略也不能保證得到最優(yōu)解。利用此策 略試解 n= 3 ,w=20,15,15, p=40,25,25, c=30 時的最優(yōu)解。雖然按 pi /wi 非遞(增)減的次序裝入物品不能保證得到最優(yōu)解，但它是一個直覺上近似的解。而且這是解決普通背包問題的最優(yōu)解，因為在選擇物品 i 裝入背包時，可以選擇物品

6、i 的一容量跳出部分，而不一定要全部裝入背包，K i < n。 貪心算法解決背包問題的算法實現(xiàn)： #include "iostream" using namespace std;struct goodinfofloat p; / 物品效益 float w; / 物品重量 float X; / 物品該放的數(shù)量 int flag; / 物品編號;/ 物品信息結(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&

7、gt;goodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0;/ 按物品效益，重量比值做升序排列void bag(goodinfo goods,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;/ 該

8、物品所要放 的量/按物品編號做降序排列 for(j=2;j<=n;j+) goods0=goodsj; i=j-1;while (goods0.flag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout<<" 最優(yōu)解為 :"<<endl;for(i=1;i<=n;i+)coutvv"第"vvivv"件物品要放："；cout<<goodsi.X<<endl;int main(void)coutvv"| 運 用

9、 貪 心 法 解 背 包 問 題|"vvendl；coutvv"|"vvendl；int i,j,n；float M；goodinfo *goods； /定義一個指針 coutvv"press v1> to run the program"vvendl； coutvv"press v0> to exit"vvendl； cin>>j；while(j)coutvv"請輸入物品的總數(shù)量："cin>>n；goods=new struct goodinfo n+1; coutv

10、v"請輸入背包的最大容量：" cin>>M;coutvvendl;for(i=1;iv=n;i+)goodsi.flag=i;coutvv"請輸入第"vvivv"件物品的重 量："cin>>goodsi.w; coutvv"請輸入第"vvivv"件物品的效 益："cin>>goodsi.p; goodsi.p=goodsi.p/goodsi.w; / 得出物品的效益，重量比coutvvendl;Insertionsort(goods,n); bag(goods,M,n);coutvv"press v1> to run agian"vvendl;cout<v"press <0> to exit"«endl; cin>>j;system("pause"); return 0;rcss <03 to exitress <1 > ta i*«ina<jianfods忙Ci ruripxiDress <0> to exit11 D:XX乍9G時sDEV93MYPROJ ECTSta