實驗報告-貪心背包.doc

《實驗報告-貪心背包.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、《算法設計與分析》實驗報告五學號：姓名：金玉琦日期：2011-11-10得分：一、實驗內容：應用貪心算法求解背包問題二、所用算法的基本思想及復雜度分析：1.貪心法貪心法是把一個復雜問題分解為一系列較為簡單的局部最優(yōu)選擇,每一步選擇都是對當前解的一個擴展,直到獲得問題的完整解。貪心法的典型應用是求解最優(yōu)化問題,而且對許多問題都能得到整體最優(yōu)解,即使不能得到整體最優(yōu)解,通常也是最優(yōu)解的很好近似。背包問題1）基本思想給定n種物品和一個容量為C的背包,物品i的重量是wi,價值為vi,背包問題是如何選擇裝入背包的物

2、品,使得裝入背包中物品的總價值最大。有3種看似合理的貪心策略：(1)選擇價值最大的物品,因為這可以盡可能快地增加背包的總價值。但是,雖然每一步選擇獲得了背包價值的極大增長,但背包容量卻可能消耗得太快,使得裝入背包的物品個數(shù)減少,從而不能保證目標函數(shù)達到最大。(2)選擇重量最輕的物品,因為這可以裝入盡可能多的物品,從而增加背包的總價值。但是,雖然每一步選擇使背包的容量消耗得慢了,但背包的價值卻沒能保證迅速增長,從而不能保證目標函數(shù)達到最大。(3)以上兩種貪心策略或者只考慮背包價值的增長,或者只考慮背包容量的

3、消耗,而為了求得背包問題的最優(yōu)解,需要在背包價值增長和背包容量消耗兩者之間尋找平衡。正確的貪心策略是選擇單位重量價值最大的物品。應用第3種貪心策略,每次從物品集合中選擇單位重量價值最大的物品,如果其重量小于背包容量,就可以把它裝入,并將背包容量減去該物品的重量,然后我們就面臨了一個最優(yōu)子問題———它同樣是背包問題,只不過背包容量減少了,物品集合減少了。因此背包問題具有最優(yōu)子結構性質。2）復雜度分析算法的時間主要消耗在將各種物品依其單位重量的價值從大到小排序。因此,算法其時間復雜性為O(nlog2n)。三．

4、源程序及注釋：#defineMAX100#include#include#includeusingnamespacestd;//設計物品屬性，重量和價值structThings{doublew;//記錄重量doublev;//記錄價值};//按單位價值降序排列intcmp(Thingsa,Thingsb){returna.v/a.w>b.v/b.w;}//貪心法背包問題函數(shù)doubleBag_Value(Thingsa[],intc,intn){d

5、oublebag_val1=0,bag_val2=0;inti=0;doubleweight_sum=0;for(intj=0;j

6、a[i].w<=c){c=c-a[i].w;bag_val1+=a[i].v;cout<<"價值為"<>n;cout<<"輸入背包的總

7、容量:";cin>>c;srand(time(0));for(i=0;i

8、背包問題類似,這兩類問題都具有最優(yōu)子結構性質,所不同的是背包問題在選擇物品裝入背包時,可以選擇一部分,而不一定要全部裝入背包,而對于0/1背包問題卻不能用貪心法求解，是由于物品不允許分割，因此,無法保證最終能將背包裝滿。所以，在編寫程序的時候需要特別注意這個問題。