Fractional KnapSack Code In C++

#include <bits/stdc++.h>
using namespace std;

bool compare(const pair<double,double>& x,const pair<double,double>& y)
{
    return (x.second>y.second);
}


int main()
{
    int i,j,k,n,m,r;
    double q=0.0,l,w,p,weight;
    vector<pair<double,double> >a;
    cin>>m;
    cin>>weight;
    for(i=1;i<=m;i++)
    {
        cin>>w>>p;
        l=(double)(p/w);
        a.push_back(make_pair(w,l));

    }
    sort(a.begin(),a.end(),compare);
    for(i=0;i<m;i++)
    {
        //cout<<a[i].first<<" "<<a[i].second<<endl;
    }

    for(i=0;i<m;i++)
    {
        //cout<<a[i].first<<" "<<weight<<endl;
        if(a[i].first<=weight)
        {
            q=q+a[i].second*a[i].first;
            weight=weight-a[i].first;

        }
        else
        {
             if(weight<=0)
             {
                 break;
             }
             //cout<<"q="<<q<<endl;
             q=q+(double)((weight/a[i].first)*(a[i].second*a[i].first));
             weight=weight-a[i].first;
        }

    }

    cout<<q<<endl;

    return 0;





}

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here