背包问题贪心算法解决

贪心算法求解背包问题

一、 实验内容

有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vin

W wi求这些物品中最有价值的一个子集。如果每次选择某（1<=i<=n），设

i 1一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次

可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。

二、 算法思想

首先计算出物品单位重量的价值vi/wi，并排序，依贪婪策略，从物品中选择可装入背包的vi/wi值最大的物品。若该物品装入背包后，背包中物品总重量未超过背包最大承重m，则选择单位重量价值次之的物品装入背包，依次策略进行下去，直到背包装满为止。

三、 实验过程（C++）

#include<iostream>

using namespace std;

//n表示背包可以存放物品的种类

//指针p指向存放物品价值的数组

//指针q指向存放物品重量的数组

void sort(int n,float *p,float *q)

{

int i;

int j;

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

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

if((*(p+i))/(*(q+i))<(*(p+j))/(*(q+j)))

{

float f;

f=*(p+i);

*(p+i)=*(p+j);

*(p+j)=f;

f=*(q+i);

*(q+i)=*(q+j);

*(q+j)=f;

}

}

void bag(int n,float m,float *v,float *w,float *x)

{

sort(n,v,w);

int i;

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

{

if(*(w+i)>m)

break;

*(x+i)=1;//可以存放该物品时，置1

m-=*(w+i);//放入后,背包的容量减少

}

//当此时背包的容量不够存放整个物品的情况时，存放一部分 if(i<n)

*(x+i)=m/(*(w+i));

if(*(x+i)!=1)

*(x+i)=0;

}

int main()

{

int m ,n,i;

cout<<"输入背包容量："<<endl;

cin>>m;

cout<<"输入物品种类："<<endl;

cin>>n;

float *w=new float[n];

float *v=new float[n];

float *x=new float[n];

cout<<"输入各种物品的重量："<<endl;

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

cin>>w[i];//各种物品的重量

cout<<"输入各种物品的价值："<<endl;

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

cin>>v[i];//各种物品的价值

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

*(x+i)=0;

bag(n,m,v,w,x);

cout<<"\n1表示要放入:"<<"\n0表示不放入："<<endl; cout<<"物品容量内容:";

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

cout<<*(w+i)<<" ";

cout<<"\n物品价值内容:";

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

cout<<*(v+i)<<" ";

cout<<"\n物品存放情况:";

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

cout<<*(x+i)<<" ";

cout<<endl;

return 0;

}

四、 实验结论

输入背包容量：

50

输入物品种类：

3

输入各种物品的重量：

26 23 15

输入各种物品的价值：

18 15 10

1表示要放入:

0表示不放入：

物品容量内容:26 15 23

物品价值内容:18 10 15

物品存放情况:1 1 0

五、 算法复杂度分析

时间复杂度为O（n2）；

Tsort = O(在此处键入公式。nlogn)； Tf（for循环复杂度为） =n2；

T = sort + Tf = O(nlogn) + O(n2) = O(n2).

本文来源：https://www.bwwdw.com/article/rqyl.html