实验五应用贪心算法求解背包问题
学院：计算机科学与技术专业：计算机科学与技术
学号：班级：姓名：
、
实验内容：
背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是n
，假设W
w
i和v
i（1 i n）w
i 1i，求这些物品中最有价值的一个子集。

如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。

二、算法思想：
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。

依此策略一直地进行下去，直到背包装满为止。

三、实验过程：
#in elude <iostream>
using n amespace std;
struct goodi nfo
{
float p; // 物品效益
float w; // 物品重量
float X; // 物品该放的数量
int flag; // 物品编号
};// 物品信息结构体
void Insertionsort(goodinfo goods[],int n)// 插入排序，按pi/wi 价值收益进行排序，一般教材上按冒泡排序
{
int j,i;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while (goods[0].p>goods[i].p)
{
}
goods[i+1]=goods[0];
}
}// 按物品效益，重量比值做升序排列goods[i+1]=goods[i];
i--;
void bag(goodinfo goods[],float M,int n)
{
float cu;
int i,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M;// 背包剩余容量for(i=1;i<n;i++)
{
if(goods[i].w<cu)// 若不超过容量，尽量增加物品{ goods[i].X=1;
cu-=goods[i].w;// 确定背包新的剩余容量
}
else
{
goods[i].X=0;
}
for(j=2;j<=n;j++) /* 按物品编号做降序排列*/
{
goods[0]=goods[j];
i=j-1;
while (goods[0].flag<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}}
goods[i+1]=goods[0];
}
coutvv"最优解为:"<<endl;
for(i=1;i<=n;i++)
{
coutvv"第"<<i<<'件物品要放："； cout<<goods[i].X<<endl; }
}
void main()
{
coutvv"| ------- 运用贪心法解背包问题
|"vvendl;
int j,n;
float M;
goodinfo *goods;// 定义一个指针
while(j)
{
cout<<" 请输入物品的总数量：";
cin>>n;
goods=new struct goodinfo [n+1];//
coutvv"请输入背包的最大容量：";
cin>>M;
cout<<endl;
int i;
for(i=1;i<=n;i++)
{
goods[i].flag=i;
coutvv"请输入第"vvivv"件物品的重量："；
cin>>goods[i].w;
coutvv"请输入第"vvivv"件物品的效益:";
cin>>goods[i].p；
goods[i].p=goods[i].p/goods[i].w;// 得出物品的效益，重量比coutvvendl;
}
Insertionsort(goods,n); bag(goods,M,n);
cout<<"press <1> to run agian"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
}
}
四、实验结果：
对于0-1 背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。

以上算法的时间和空间复杂度为O(n*n) ，其中时间复杂度基本已经不能再优化了，但空间复杂度可以优化到O(n)。