beibao.c

c++程序设计与分析,进行信息学竞赛的试题分析与解答

#define N 100
float M,V;
struct beibao{
float v;
float w;
float a;
int n;
float flag;
}xx[N];
void swap(struct beibao *a,struct beibao *b)
{struct beibao c;
 c=*a;*a=*b;*b=c;
}
/*void sort(int n,struct beibao xx[])
{int i,j;
 for(i=1;i<=n;i++)
  for(j=1;j<=n-i;j++)
   if(xx[j].a<xx[j+1].a)
    swap(&xx[j],&xx[j+1]);
}*/
void QuickSort(struct beibao a[],int p,int r)
{if(p<r)
 {int q=Partition(a,p,r);
  QuickSort(a,p,q-1);
  QuickSort(a,q+1,r);
 }
}
int Partition(struct beibao a[],int p,int r)
{int i=p,j=r+1;
 struct beibao x=a[p];
 struct beibao b;
 while(1)
 {while(a[++i].a>x.a) if(i==r) break;
  while(a[--j].a<x.a) if(j==0) break;
  if(i>=j) break;
  b=a[i];a[i]=a[j];a[j]=b;
 }
 a[p]=a[j];a[j]=x;
 return j;
}
void Knapsack(int n,struct beibao xx[])
{int i,j;
 float c;
 for(j=1;j<=n;j++) {xx[j].a=xx[j].v/xx[j].w;xx[j].flag=0;xx[j].n=j;}
 QuickSort(xx,1,n);
 c=M;
 for(i=1;i<=n;i++)
  {if(xx[i].w>c) break;
   xx[i].flag=1;
   c-=xx[i].w;
  }
 if(i<=n) xx[i].flag=c/xx[i].w;
}
void main()
{
 int n,i;
 printf("please input n:");
 scanf("%d",&n);
 printf("please input w[i]:");
 for(i=1;i<=n;i++)  scanf("%f",&xx[i].w);
 printf("please iuput v[i]:");
 for(i=1;i<=n;i++)  scanf("%f",&xx[i].v);
 printf("please iuput M:");
 scanf("%f",&M);
 Knapsack(n,xx);
 printf("the answer is:");
 for(i=1;xx[i].flag!=0;i++) printf("\nx[%d]=%f",xx[i].n,
 xx[i].flag);
 for(i=1;i<=n;i++) V=V+xx[i].flag*xx[i].v;
 printf("\nthe total v is:%f",V);
 getch();
}