Knapsack.txt

/*
Knapsack Problem using greedy
*/

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  float m;
  cout<<"Enter n and m:";
  cin>>n>>m;
  float a[2][n];
  cout<<"Enter values and weights\n";
  for(int i=0;i<n;i++){
    cin>>a[0][i];
    cin>>a[1][i];
  }
   float ans[n];
  for(int i=0;i<n;i++)
    ans[i]=0;
  vector< pair <float,int> >x;
  for(int i=0;i<n;i++){
   float j=a[0][i]/a[1][i];
   x.push_back(make_pair(j,i));
  }
  sort(x.begin(),x.end());
  int y=n-1;
  int i=0,j;
  float u=m;
  while(i<n){
   j=x[y].second;
   if(a[1][j]>u) break;
   ans[j]=1;
   u=u-a[1][j];
   i++;
   y--;
  }
  if(i!=n-1) ans[j]=u/a[1][j];
  cout<<"Fractions of different items are:\n";
  for(int i=0;i<n;i++)
   cout<<ans[i]<<" ";
  return 0;
}

Output:
Enter n and m:3 20
Enter values and weights
25 18
24 15
15 10
Fractions of different items are:
0 1 0.5