题目：载重量为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;
}
这是我写的，不知道为什么调用合并排序，结果就是不对。。求助高手啊！！！

为什么代码这么复杂啊，你这种背包问题只要按价值排序，然后从价值最大的开始往里面放 放到背包满了，输出最大值就OK了；

复杂的是排序，因为要使时间复杂度最低

排序你可以用2个FOR循环来搞定，不过这效率不怎么高，还有就是用快排，但不知道你会不

好像不用这么复杂，求出每个物品的单位重量价值即pi/wi，在以此为权排序。由大到小装包直到满为止。

那就用背包做了

我是想问为什么调用合并排序会错，题目要求时间复杂度最低