(132). 33.4 FRACTIONAL KNAPSACK‐GREEDY ALGORITHMS - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

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

#define pii pair<int, int> #define vii vector #define rap(i, a, b) for (int i = a; i < b; ++i) #define rep(i, a, b) for (int i = a; i <= b; ++i)

bool compare(pii p1, pii p2) { double v1 = (double)p1.first / p1.second; double v2 = (double)p2.first / p2.second;

return v1 > v2;

}

int main() { int n; cout << "Enter the number of items: "; cin >> n;

vii a(n);
cout << "Enter the values and its weights: " << endl;
rap(i, 0, n) {
    cin >> a[i].first >> a[i].second;
}

int w;
cout << "Enter the weight: ";
cin >> w;

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

int ans = 0;
rap(i, 0, n) {
    if (w >= a[i].second) {
        ans += a[i].first;
        w -= a[i].second;
        continue;
    }

    double vw = (double)a[i].first / a[i].second;
    ans += w * vw;  // Fix: Corrected the calculation of the partial value.
    w = 0;
    break;
}

cout <<"Maximum values of items: "<<ans << endl;

return 0;

}

/* OUTPUT:- Enter the number of items: 5 Enter the values and its weights: 21 7 24 4 12 6 40 5 30 6 Enter the weight: 20 Maximum values of items: 109 */

⚠️ **GitHub.com Fallback** ⚠️