求助:背包问题,用贪心算法
题目:载重量为M的背包,重量为wi,价值为pi的物体,1<=i<=n,白物体装满背包,使背包内的物体价值最大,物体可以分割。#include<iostream.h>
typedef struct
{
float p;
float w;
float v;
}OBJECT;
void merge(OBJECT instance[],int p,int q,int r ,int m)
{
OBJECT *bp=new OBJECT[m];
int i,j,k;
i=p;
j=q+1;
k=0;
while(i<=q && j<=r)
{
if(instance.v>=instance[j].v)
bp[k++]=instance[i++];
else
bp[k++]=instance[j++];
}
if(i==q+1)
{
for(;j<=r;j++)
bp[k++]=instance[j];
}
else
{
for(;i<=q;i++)
bp[k++]=instance;
}
k=0;
for(i=p;i<=r;i++)
instance=bp[k++];
delete bp;
}
void merge_sort(OBJECT instance[],int n)
{
int s,t,i=1;
while(t<n)
{
s=t;
t=2*s;
i=0;
while(i+t<n)
{
merge(instance,i,i+s-1,i+t-1,t);
i=i+t;
}
if(i+s<n)
merge(instance,i,i+s-1,n-1,n-i);
}
}
float knapsack_greedy(float M,OBJECT instance[],float x[],int n)
{
int i;
float m,p=0;
for(i=0;i<n;i++)
{
instance.v=instance.p/instance.w;
x=0;
}
merge_sort(instance,n);
m=M;
for(i=0;i<n;i++)
{
if(instance.w<=m)
{
x=1;
m-=instance.w;
p+=instance.p;
}
else
{
x=m/instance.w;
p+=x*instance.p;
break;
}
}
return p;
}
int main()
{
int i,n;
float m,p;
cout<<"输入物体个数:";
cin>>n;
cout<<"输入背包载重量:";
cin>>m;
OBJECT *instance=new OBJECT[n];
float *x=new float[n];
for(i=0;i<n;i++)
{
cout<<"输入物品价值:";
cin>>instance.p;
cout<<"输入物品重量:";
cin>>instance.w;
}
p=knapsack_greedy(m,instance,x,n);
for(i=0;i<n;i++)
cout<<"第"<<i<<"件物品要放:"<<x<<endl;
cout<<endl<<"得到背包的总价值:"<<p<<endl;
return 0;
}
这是我写的,不知道为什么调用合并排序,结果就是不对。。求助高手啊!!!