C應用貪心算法求解背包問題

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

2、多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。三、實驗過程：#include <iostream>using namespace std;struct goodinfofloat p; /物品效益 float w; /物品重量 float X; /物品該放的數(shù)量 int flag; /物品編號;/物品信息結(jié)構(gòu)體void Insertionsort(goodinfo goods,int n)/插入排序，按pi/wi價值收益進行排序，一般教材上按冒泡排序int j,i; for(j=2;j<=n;j+) goods0=goodsj; i=j-1; while (good

3、s0.p>goodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i<=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;i<n;i+) if(goodsi.w<cu)/若不超過容量，盡量增加物品 goodsi.X=1; cu-=goodsi.w;/確定背包新的剩余容量else goodsi.X=0; for(j=2;j<=n;j+)

4、 /*按物品編號做降序排列*/ goods0=goodsj; i=j-1; while (goods0.flag<goodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout<<"最優(yōu)解為:"<<endl; for(i=1;i<=n;i+) cout<<"第"<<i<<"件物品要放:" cout<<goodsi.X<<endl; void main() cout<<"|

5、-運用貪心法解背包問題-|"<<endl; int j,n; float M; goodinfo *goods;/定義一個指針 while(j) cout<<"請輸入物品的總數(shù)量：" cin>>n; goods=new struct goodinfo n+1;/ cout<<"請輸入背包的最大容量：" cin>>M; cout<<endl; int i; for(i=1;i<=n;i+) goodsi.flag=i; cout<<"請輸入第&qu

6、ot;<<i<<"件物品的重量:" cin>>goodsi.w; cout<<"請輸入第"<<i<<"件物品的效益:" cin>>goodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 cout<<endl; Insertionsort(goods,n); bag(goods,M,n); cout<<"press <1> to run agian"<<endl; cout<<"press <0> to exit"<<endl; cin>>j;四、實驗結(jié)果：對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為