#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
float n,m,loc,max,ps,temp,i,k;
float x[100],v[100],p[100],w[100];

cout<<endl<<"-------- KNAPSACK Problem using Greedy Method --------"<<endl<<endl;
cout<<"Enter Total No. of Objects = ";
cin>>n;
cout<<"Enter Capacity of Knapsack = ";
cin>>m;

cout<<endl<<endl;

for(i=1;i<=n;i++)                 // INPUT :- Weight and Profit of Objects  
{
cout<<"Enter Profit of Object "<<i<<" = ";
cin>>p[i];
cout<<"Enter Weight of Object "<<i<<" = ";
cin>>w[i];
v[i]=p[i]/w[i];
cout<<"Profit per unit of Object "<<i<<" is = "<<v[i]<<endl<<endl<<endl;
x[i]=0.0;
}

for(ps=1;ps<=n-1;ps++)     // SORTING the Values of Profit Per Unit --> v[i]
{                          // using Selection Sort Algorithm 
max=v[ps];
loc=ps;

for(k=ps+1;k<=n;k++)
{
if(max<v[k])
{
max=v[k];
loc=k;
}
}
temp=v[ps];
v[ps]=v[loc];
v[loc]=temp;

temp=p[ps];
p[ps]=p[loc];
p[loc]=temp;

temp=w[ps];
w[ps]=w[loc];
w[loc]=temp;
}

cout<<endl<<endl<<endl;
cout<<"After Arranging the Objects :-"<<endl<<endl;

for(i=1;i<=n;i++)
{
cout<<"Profit of Object "<<i<<" is = "<<p[i]<<endl;
cout<<"Weight of Object "<<i<<" is = "<<w[i]<<endl;
cout<<"Profit per unit of Object "<<i<<" is = "<<v[i]<<endl<<endl<<endl;
}

for(i=1;i<=n;i++)      // Greedy Knapsack Algo to Find Fraction of Objects 
{
if(w[i]>m)
break;

x[i]=1.0;
m=m-w[i];
}

if(i<=n)
x[i]=m/w[i];


float TP=0, TW=0;
for(i=1;i<=n;i++)
{
cout<<"Fraction of Object "<<i<<" is = "<<x[i]<<endl<<endl;

TP=TP+(p[i]*x[i]);               // Finding Total Profit, Total Weight  
TW=TW+(w[i]*x[i]);
}

cout<<endl<<"Optimal Solution :-"<<endl<<endl;

cout<<"Total Profit = "<<TP<<endl;
cout<<"Total Weight = "<<TW;

getch();
}