實(shí)驗(yàn)報(bào)告-貪心背包.doc

《實(shí)驗(yàn)報(bào)告-貪心背包.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

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

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

4、源程序及注釋?zhuān)?defineMAX100#include#include#includeusingnamespacestd;//設(shè)計(jì)物品屬性，重量和價(jià)值structThings{doublew;//記錄重量doublev;//記錄價(jià)值};//按單位價(jià)值降序排列intcmp(Thingsa,Thingsb){returna.v/a.w>b.v/b.w;}//貪心法背包問(wèn)題函數(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<<"價(jià)值為"<>n;cout<<"輸入背包的總

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

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