Wednesday, 28 November 2012

knapsack fraction problem algorithm


//knapsack fraction problem algorithm implementation.
#include<stdio.h>
#include<conio.h>

void main()
{
 clrscr();
 int w[20],v[20],s[20],nw,W,x,i,j,temp,profit=0;
 printf("Enter total no. of weights:");
 scanf("%d",&nw);
 printf("Maximum capacity:");
 scanf("%d",&W);
 for(i=0;i<nw;i++)
 {
  printf("Enter weight %d:",i+1);
  scanf("%d",&w[i]);
  printf("Enter value:");
  scanf("%d",&v[i]);
  s[i]=v[i]/w[i];
 }
 for(i=0;i<nw;i++)
 {
  for(j=i;j<nw;j++)
  {
   if(w[j]<w[i])
   {
    temp=w[j];w[j]=w[i];w[i]=temp;
    temp=v[j];v[j]=v[i];v[i]=temp;
    temp=s[j];s[j]=s[i];s[i]=temp;
   }
  }
 }
 for(i=0;W>0;i++)
 {
  if (w[i]<W)
  {
   x=1;W=W-w[i];
  }
  else
  {
   x=W/w[i];W=0;
  }
  profit=profit+(v[i]*x);
 }
 printf("Maximum Profit is: %d",profit);
 getch();
}
//program written by Mars.

No comments:

Post a Comment

You are welcome, your comment helps me to make this blog more better.