1、 背包問題貪心方法 實(shí)驗(yàn)日志 實(shí)驗(yàn)題目：1）求以下情況背包問題的最優(yōu)解：n=7，M=15，（）=（10，5，15，7，6，18，3）和（）=（2，3，5，7，1，4，1）。實(shí)驗(yàn)?zāi)康模?. 掌握貪心方法算法思想；2. 熟練使用貪心算法之背包問題解決相應(yīng)的問題。實(shí)驗(yàn)思想：貪心方法是一種改進(jìn)了的分級(jí)處理方法。它首先根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序，并按排序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此解輸入加到這部分解中。這種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法稱為貪心方法。1背包問題（1）背包問題的描述

2、：已知有n種物品和一個(gè)可容納M重量的背包，每種物品i的重量為。假定將物品i的一部分放入背包就會(huì)得到的效益，這里，, 。顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總重量不得超過M.。如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益?，F(xiàn)需解決的問題是，這些物品重量的和大于M，該如何裝包。由以上敘述，可將這個(gè)問題形式表述如下：極 大 化 約束條件 （2）用貪心策略求解背包問題首先需選出最優(yōu)的量度標(biāo)準(zhǔn)。不妨先取目標(biāo)函數(shù)作為量度標(biāo)準(zhǔn)，即每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度標(biāo)準(zhǔn)下的貪心方法就是按效益值的非增次序?qū)⑽锲芬患诺奖嘲腥?。如果正在考慮

3、中的物品放不進(jìn)去，則可只取其一部分來(lái)裝滿背包。但這最后一次的方法可能不符合使背包每次獲得最大效益增量的量度標(biāo)準(zhǔn)，這可以換一種能獲得最大增量的物品，將它（或它的一部分）放入背包，從而使最后一次裝包也符合量度標(biāo)準(zhǔn)的要求。算法如下所示。 算法21 背包問題的貪心算法procedure GREEDY-KNAPSACK(P,W,M,X,n) /P（1：n）和W（1：n）分別含有按P（i）/W（i）P（i+1）/ W （i+1）排序的n件物品的效益值和重量。M是背包的容量大笑，而X（1：n）是解向量。/ real P(1：n)，W（1：n）,X（1：n），M，cu； integer i，n;X0 /將解向

4、量初始化為零cuM /cu是背包剩余容量for i1 to n do if W(i)>cu then exit endif X(i) 1 cucu-W(i)repeatif in then X(i) cu/W(i)endifend GREEDY-KNAPSACK實(shí)驗(yàn)代碼：#include<iostream>using namespace std;void beibao(double *w,double *v,double *x,double n,double *C)int i,j,temp;for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)if(

5、vi/wi<vj/wj)temp=vi;vi=vj;vj=temp;temp=wi;wi=wj;wj=temp;for(i=0;i<n;i+)xi=0;for(i=0;*C!=0;i+)if(wi<*C)xi=wi;*C=*C-wi;elsexi=*C;*C=*C-*C;void main()int i;double *w,*v,n,C;double *x;cout<<"請(qǐng)輸入物品數(shù)"<<endl;cin>>n;w=new double(n);/動(dòng)態(tài)分配內(nèi)存v=new double(n);x=new double(n);

6、cout<<"請(qǐng)輸入背包的容量"<<endl;cin>>C;cout<<"請(qǐng)分別輸入"<<n<<"個(gè)物品的重量:"<<endl;for(i=0;i<n;i+)cin>>wi;cout<<"請(qǐng)分別輸入"<<n<<"個(gè)物品的價(jià)值:"<<endl;for(i=0;i<n;i+)cin>>vi;beibao(w,v,x,n,&C);cout<<"裝入的物品為:"<<endl;for(i=0;i<n;i+)if(xi!=0)cout<<"其裝的重量為："<<xi<&