knapsack.c

knapsack sort is a sorting algo

#include<stdio.h>
#include<conio.h>

void read(int *array , int n)
{
     int i;
     for(i = 0;i<n;i++)
           scanf("%d",&array[i]);
}

void sort(int *weight , int *profit , int *name , int n )
{
     int i,j;
     float ratio1 , ratio2;
     for(i=0;i<n;i++)
     {
          for(j=0;j<n-i-1;j++)
          {
               ratio1 = (float )profit[j]/weight[j];
               ratio2 = (float )profit[j+1]/weight[j+1];
               if( ratio1 < ratio2 )
               {
                       weight[j] ^= weight[j+1] ^= weight[j] ^= weight[j+1];
                       profit[j] ^= profit[j+1] ^= profit[j] ^= profit[j+1];
                       name[j] ^= name[j+1] ^= name[j] ^= name[j+1];
               }
          }
     }
}

void display(int *array , int n)
{
     int i;
     for(i = 0;i<n;i++)
          printf("%d ",array[i]);
}

void algo(int *weight ,int *profit , float *fraction , int n , int capacity,float *totalProfit)
{
      int i ;
      for(i = 0;i<n;i++)
            fraction[i] = 0.0;
      i = 0;      
      while(i != n)
      {
            
            if(weight[i] > capacity)
                         break;
     
            else
            {
                         fraction[i] = 1;
                         capacity -= weight[i];
            }
            *totalProfit = *totalProfit +  fraction[i]*profit[i];
            i++;
            
      }
      if(i <= n-1)
      {
           fraction[i] = (capacity*1.0/weight[i]);
           *totalProfit = *totalProfit +  fraction[i]*profit[i];
      }
           
      
}
int main()
{
      int *profit , *weight , *name ,  capacity , n,i,count = 0;
      float *fraction , totalProfit = 0;
      printf("\n\nEnter the total no. of items : ");
      scanf("%d",&n);
      
      printf("\n\nEnter the max Capacity of  Knapsack : ");
      scanf("%d",&capacity);
      
      profit = (int *)malloc(n*sizeof(int));
      weight = (int *)malloc(n*sizeof(int));
      name = (int *)malloc(n*sizeof(int));
      fraction = (float *)malloc(n*sizeof(float));
      printf("\nEnter the weights of %d items : \n",n);
      read(weight , n);
      
      printf("\nEnter the profits associated with the %d items : \n",n);
      read(profit , n);
      
      for(i=1;i<=n;i++)
           name[i-1] = i;
      
      sort(weight,profit,name ,n);

      for(i=0;i<n;i++)
           printf("%d ",name[i]);
      
      algo(weight ,profit ,  fraction , n , capacity, &totalProfit);
      
      printf("\n\nThe optimal Solution is : \n");
      for(i = 0;i<n;i++)
            printf("\nItem : %d          Fraction : %.3f",name[i],fraction[i]);
      printf("\nTotal Profit = %.3f",totalProfit);
      getch();
      return 0;
}