# include

void knapsack(int n, float w[], float p[], float m){
 float x[20], tp= 0;
 int i, j, u;

 for (i=0; i < n; i++ ){
  x[i]=0.0;
 }
 u=m;

 for (i=0; i < n; i++ ){
  if(w[i]>u)
   break;
  else{
   x[i]=1.0;
   tp= tp+p[i];
   u=u-w[i];
  }

  if(i < n){
   x[i]=u/w[i];
  }

  tp= tp + (x[i]*p[i]);
  printf("\n The path is: ");
  for(i=0; i < n; i++ ){
   printf("%f\t",x[i]);
  }
  printf("\n Maximum profit is: %f", tp);
 }

 float swap(float *a, float *b){
  float temp;
  temp= *a;
  *a= *b;
  *b= temp;
 }
}


int main(){
 float w[20], p[20], m;
 int n, i ,j;
 float ratio[20], temp;

 printf ("\n Enter the number of objects: ");
 scanf ("%d", &n);
 printf ("\n Enter the weights and profits of each object: ");
 for (i=0; i < n; i++){
 scanf("%f %f", &w[i], &p[i]);
 }

 printf ("\nEnter the size of knapsack: ");
 scanf ("%f", &m);
 for (i=0; i < n; i++){
 ratio[i]=p[i]/w[i];
 }

 for( i=0; i < n; i++ ){
  for(j=i+1; j < n; j++){
   if(ratio[i] < ratio[j]){
    swap(&ratio[i], &ratio[j]);
    swap(&w[i], &w[j]);
    swap(&p[i], &p[j]);
   }
  }
 }
 knapsack(n, w, p, m);
}