贪心算法求解背包问题
一、 实验内容
有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vin
Wwi求这些物品中最有价值的一个子集。如果每次选择某（1
i1一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次
可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。
二、 算法思想
首先计算出物品单位重量的价值vi/wi，并排序，依贪婪策略，从物品中选择可装入背包的vi/wi值最大的物品。若该物品装入背包后，背包中物品总重量未超过背包最大承重m，则选择单位重量价值次之的物品装入背包，依次策略进行下去，直到背包装满为止。
三、 实验过程（C++）
#include
using namespace std;
//n表示背包可以存放物品的种类
//指针p指向存放物品价值的数组
//指针q指向存放物品重量的数组
void sort(int n,float *p,float *q)
{
int i;
int j;
for(i=0;i
for(j=i+1;j
if((*(p+i))/(*(q+i))
{
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
{
if(*(w+i)>m)
break;
*(x+i)=1;//可以存放该物品时，置1
m-=*(w+i);//放入后,背包的容量减少
}
//当此时背包的容量不够存放整个物品的情况时，存放一部分 if(i
*(x+i)=m/(*(w+i));
if(*(x+i)!=1)
*(x+i)=0;
}
int main()
{
int m ,n,i;
cout
cin>>m;
cout
cin>>n;
float *w=new float[n];
float *v=new float[n];
float *x=new float[n];
cout
for(i=0;i
cin>>w[i];//各种物品的重量
cout
for(i=0;i
cin>>v[i];//各种物品的价值
for(i=0;i
*(x+i)=0;
bag(n,m,v,w,x);
cout
for(i=0;i
cout
cout
for(i=0;i
cout
cout
for(i=0;i
cout
cout
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).
贪心算法求解背包问题
一、 实验内容
有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vin
Wwi求这些物品中最有价值的一个子集。如果每次选择某（1
i1一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次
可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。
二、 算法思想
首先计算出物品单位重量的价值vi/wi，并排序，依贪婪策略，从物品中选择可装入背包的vi/wi值最大的物品。若该物品装入背包后，背包中物品总重量未超过背包最大承重m，则选择单位重量价值次之的物品装入背包，依次策略进行下去，直到背包装满为止。
三、 实验过程（C++）
#include
using namespace std;
//n表示背包可以存放物品的种类
//指针p指向存放物品价值的数组
//指针q指向存放物品重量的数组
void sort(int n,float *p,float *q)
{
int i;
int j;
for(i=0;i
for(j=i+1;j
if((*(p+i))/(*(q+i))
{
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
{
if(*(w+i)>m)
break;
*(x+i)=1;//可以存放该物品时，置1
m-=*(w+i);//放入后,背包的容量减少
}
//当此时背包的容量不够存放整个物品的情况时，存放一部分 if(i
*(x+i)=m/(*(w+i));
if(*(x+i)!=1)
*(x+i)=0;
}
int main()
{
int m ,n,i;
cout
cin>>m;
cout
cin>>n;
float *w=new float[n];
float *v=new float[n];
float *x=new float[n];
cout
for(i=0;i
cin>>w[i];//各种物品的重量
cout
for(i=0;i
cin>>v[i];//各种物品的价值
for(i=0;i
*(x+i)=0;
bag(n,m,v,w,x);
cout
for(i=0;i
cout
cout
for(i=0;i
cout
cout
for(i=0;i
cout
cout
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).