Fractional knapsack

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

typedef pair<int, int> p;
vector<p>v;

bool compare(p A, p B)
{
    return A.second * B.first > B.second * A.first;
}

void fractional_knapsack()
{
    int n, value, weight, want_weight, i;

    cout << "Enter Array Size :: ";
    cin >> n;

    cout << "Enter Weight and Value :: " << endl;
    for(i=1;i<=n;i++)
    {
        cin >> weight >> value;
        v.push_back(p(weight, value));
    }

    sort(v.begin(), v.end(), compare);

    cout << "Total Weight :: ";
    cin >> want_weight;

    double ans = 0;

    for(i=0;i<n;i++)
    {
        int z = min(want_weight, v[i].first);
        want_weight = want_weight - z;
        ans = ans + z*(double)(v[i].second/v[i].first);
    }

    cout << "Maximum Cost :: " << ans << endl;
}
int main()
{
    fractional_knapsack();

    return 0;
}

Comments