C++應(yīng)用貪心算法求解背包問題

1、實驗五應(yīng)用貪心算法求解背包問題學(xué)院：計算機(jī)科學(xué)與技術(shù)專業(yè)：計算機(jī)科學(xué)與技術(shù)學(xué)號：班級：姓名：一、實驗內(nèi)容：背包問題指的是：有一個承重為W的背包和n個物品，它們各自的重量和價值分別是w和v(1in)，假設(shè)W，工w，求這些物品中最有價值的一個子集。如果每次選擇iiii=1某一個物品的時候，只能全部拿走，則這一問題稱為離散(0-1)背包問題；如果每次可以拿走某一物品的任意一部分，則這一問題稱為連續(xù)背包問題。二、算法思想：首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值

2、次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。三、實驗過程：#includeusingnamespacestd;structgoodinfofloatp;/物品效益floatw;/物品重量floatX;/物品該放的數(shù)量intflag;/物品編號;/物品信息結(jié)構(gòu)體voidInsertionsort(goodinfogoods,intn)插入排序，按pi/wi價值收益進(jìn)行排序，一般教材上按冒泡排序intj,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益，重量比值做升序排列voidbag(good

3、infogoods,floatM,intn)floatcu;inti,j;for(i=1;i=n;i+)goodsi.X=0;cu=M;/背包剩余容量for(i=1;in;i+)if(goodsi.wvcu)若不超過容量，盡量增加物品goodsi.X=1;cu-=goodsi.w;確定背包新的剩余容量elsegoodsi.X=0;for(j=2;j=n;j+)/*按物品編號做降序排列*/goods0=goodsj;i=j-1;while(goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;coutvv最優(yōu)解為:vvendl;for

4、(i=1;in;goods=newstructgoodinfon+1；/coutvv請輸入背包的最大容量：；cinM；coutvvendl；inti；for(i=1；iv=n；i+)goodsi.flag=i；coutvv請輸入第vvivv件物品的重量:；cingoodsi.w；coutvv請輸入第vvivv件物品的效益:；cingoodsi.p；goodsi.p=goodsi.p/goodsi.w;得出物品的效益，重量比coutvvendl；Insertionsort(goods,n)；bag(goods,M,n)；coutvvpressv1torunagianvvendl；coutvvpressv0toexitvvendl；cinj；四、實驗結(jié)果：對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公