Fractional Knapsack

There are n items in a store. For i =1,2, . . . , n, item i has weight wi > 0 and worth vi > 0. Thief can carry a maximum weight of W pounds in a knapsack. In this version of a problem the items can be broken into smaller piece, so the thief may decide to carry only a fraction xi of object i, where 0 ≤ xi ≤ 1. Item i contributes xiwi to the total weight in the knapsack, and xivi to the value of the load.here are n items in a store.




Source Code:-



#include<iostream.h>
#include<conio.h>

void knapsack(float*,float*,float,float);
void  main()
{ clrscr();
  float value[50],weight[50],max,i,n;
  cout<<"Program for Fractional knapsack by-Tarun Rawat \n\n";
  cout<<"Enter the maximum capacity of knapsack: ";
  cin>>max;
  cout<<"Enter the number of item: ";
  cin>>n;
  cout<<"Enter the values of item,according to per unit value in descending order:\n";
  for( i=0;i<n;i++)
  {cin>>value[i];
  }
  cout<<"Enter the values of weight according to value of item:\n";
   for( i=0;i<n;i++)
  {cin>>weight[i];
  }
  cout<<"Elements enter by you is \n";
  for( i=0;i<n;i++)
  {cout<<"\nvalue "<<value[i]<<" weight "<<weight[i];
  }
  knapsack(value,weight,max,n);
getch();
}

void knapsack(float value[],float weight[],float max,float n)
  { float current=0,i=0,rem;
    float currentval=0;
      while((current<=max)&& (weight[i]<=max-current))
       {    current=current+weight[i];
        currentval=currentval+value[i];
        i++;
        }
     rem=max-current;
    if(current<max)
       {current =current+rem;
       currentval=currentval+((rem * value[i])/weight[i] );
       }

   cout<<"\n\nmaximum profit is: "<<currentval;
   cout<<"\ncurrent weight is: "<<current;
  }