2贪心算法解决部分背包问题

2贪心算法解决部分背包问题

一、实验目的

学习掌贪心算法法思想。

二、实验内容

用贪心法解决部分背包问题。给定n种物品和一个背包。物品i的重量是Wi，其价值为pi，背包的容量为M，将物品i的一部分xi放入背包会得到pi xi的效益。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?给出具体的装包方案。在选择装入背包的物品时，对每种物品i，可以整件装入背包、不装入背包或部分装入背包。但不能将物品i装入背包多次。

四、需求分析

对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。

五、基本思想：

贪婪法是解决最优化问题时的一种简单但适用范围有限的策略。总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品。

六、详细设计

#include<iostream>

using namespace std;

struct _Object//物品结构体

{

int Value;//物品价值

int Weight;//物品重量

int AveValue;//物品单位价值

float Num;//物品可以放入的数量

void knaspsack(int n,float M,_Object object[])

{ //n为物品个数，M为背包容量

int i;

float C=M;

for(i=0;i<n;i++)

{

object[i].Num=0;//初始化放入背包的物品为0

if(object[i].Weight>C)break;//当物品重量大于背包容量时

else//小于时

{

object[i].Num=1;//物品i放入一件

C-=object[i].Weight;//背包容量减小

}

}

if(i<=n)//当不能放入整个物品时，选取物品一部分放入

object[i].Num=C/object[i].Weight;

for(i=0;i<n;i++)

{

if(object[i].Num>0)

cout<<"重量为: "<<object[i].Weight<<" 价值为: "<<object[i].Value<<" 的物品

放入"<<object[i].Num<<" 件"<<endl;

}

}

void SortObject(_Object object[],int n)//将各个物品按单位价值进行排序

{

int j;

_Object temp;

int i;

for(i=0;i<n;i++)

object[i].AveValue=object[i].Value/object[i].Weight;//各个物品的单位价值 for(i=0;i<n-1;i++)//根据物品的单位价值对物品进行从大到小的冒泡排序

{

for(j=0;j<n-i-1;j++)

{

if(object[j].AveValue<object[j+1].AveValue)

{

temp=object[j];

object[j]=object[j+1];

object[j+1]=temp;

}

}

}

}

int main()

{

_Object object[4];//4个物品

int M=9;//背包容量为15

object[0].Weight=2;object[0].Value=3;

object[1].Weight=3;object[1].Value=4;

object[2].Weight=4;object[2].Value=5;

object[3].Weight=5;object[3].Value=7;

SortObject(object,4);

knaspsack(4,M,object);

}

七、结果分析：

对于0-1背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满，部分闲置的背包空间，使每

公斤背包的价值降低了。以上算法的时间复杂度和空间复杂度为 O(n*n)，其中时间复杂度基本已经不能再优化了，但空间复杂度可以优化到O（n).