0-1背包問(wèn)題四種不同算法的實(shí)現(xiàn)

《0-1背包問(wèn)題四種不同算法的實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院題目0-1背包問(wèn)題算法實(shí)現(xiàn)院系數(shù)理院專業(yè)班級(jí)信計(jì)09學(xué)生姓名雷雪艷學(xué)號(hào)200905130指導(dǎo)教師李秦二Ｏ一二年六月五日一、問(wèn)題描述：1、0—1背包問(wèn)題：給定n種物品和一個(gè)背包，背包最大容量為M，物品i的重量是wi,其價(jià)值是平Pi，問(wèn)應(yīng)當(dāng)如何選擇裝入背包的物品，似的裝入背包的物品的總價(jià)值最大？背包問(wèn)題的數(shù)學(xué)描述如下：2、要求找到一個(gè)n元向量(x1，x2…xn)，在滿足約束條件：情況下，使得目標(biāo)函數(shù)，其中，1in；M>0；wi>0；pi>0。滿足約束條件的任何向量都是一個(gè)可行解，而使得目標(biāo)函數(shù)達(dá)到

2、最大的那個(gè)可行解則為最優(yōu)解[1]。給定n種物品和1個(gè)背包。物品i的重量是wi，其價(jià)值為pi，背包的容量為M。問(wèn)應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價(jià)值最大？在選擇裝人背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包、不裝入背包。不能將物品i裝人背包多次，也不能只裝入部分的物品i。該問(wèn)題稱為0-1背包問(wèn)題。0-1背包問(wèn)題的符號(hào)化表示是，給定M>0，wi>0，pi>0，1in，要求找到一個(gè)n元0-1向量向量(x1，x2…xn)，Xi=0或1,1in,使得，而且達(dá)到最大[2]。二、解決方案：方案一：貪心算法1、貪心算

3、法的基本原理與分析貪心算法總是作出在當(dāng)前看來(lái)是最好的選擇，即貪心算法并不從整體最優(yōu)解上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好近似解。貪心算法求解的問(wèn)題一般具有兩個(gè)重要性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)解的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法

4、的主要區(qū)別。當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、0-1背包問(wèn)題的實(shí)現(xiàn)對(duì)于0-1背包問(wèn)題，設(shè)A是能裝入容量為c的背包的具有最大價(jià)值的物品集合，則Aj=A-{j}是n-1個(gè)物品1,2,...,j-1,j+1,...,n可裝入容量為c-wj的背包的具有最大價(jià)值的物品集合。用貪心算法求解0-1背包問(wèn)題的步驟是，首先計(jì)算每種物品單位重量的價(jià)值vi/wi；然后，將物品進(jìn)行排序，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝

5、入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總量未超過(guò)c，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直進(jìn)行下去，直到背包裝滿為止。3、算法設(shè)計(jì)如下：#include#definemax100//最多物品數(shù)voidsort(intn,floata[max],floatb[max])//按價(jià)值密度排序{intj,h,k;floatt1,t2,t3,c[max];for(k=0;k

6、){t1=a[j];a[j]=a[j+1];a[j+1]=t1;t2=b[j];b[j]=b[j+1];b[j+1]=t2;t3=c[j];c[j]=c[j+1];c[j+1]=t3;}}voidknapsack(intn,floatlimitw,floatv[max],floatw[max],intx[max]){floatc1;//c1為背包剩余可裝載重量inti;sort(n,v,w);//物品按價(jià)值密度排序c1=limitw;for(i=0;ic1)break;x[i]=1;//x[

7、i]為1時(shí)，物品i在解中c1=c1-w[i];}}voidmain(){intn,i,x[max];floatv[max],w[max],totalv=0,totalw=0,limitw;cout<<"請(qǐng)輸入n和limitw:";cin>>n>>limitw;for(i=1;i<=n;i++)x[i]=0;//物品選擇情況表初始化為0cout<<"請(qǐng)依次輸入物品的價(jià)值："<>v[i];cout<

8、1;i<=n;i++)cin>>w[i];cout<