// C/C++ program to solve fractional Knapsack Problem
#include <bits/stdc++.h>

using namespace std;

// Struktura Item beleži težinu, cenu i inicijalnu poziciju svakog člana niza.
// Zbog sortiranja unutar funkcije, permutovaće se redosled članova pa se neće
// vratiti željena vrednost.
struct Item
{
    int value, weight, position;

    // Konstruktor
    Item(int value, int weight, int position)
      : value(value), weight(weight), position(position) {}
};

// Funkcija po kojoj se sortiraju članovi niza po opadajućem odnosu cene i težine
bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

// Vraća koji su  predmeti poneti, tako što rezultat predstavlja zbir
// rednih broja predmeta stepenovanih na broj dva.
// Npr. ako su korišćeni prvi, četvrti i sedmi predmet,
// used_items = 2^1 + 2^4 + 2^7 - jedinstveno zapisujemo uzete predmete.
double fractionalKnapsack(int weight, struct Item arr[], int n)
{
    // Sortiranje prvih n članova niza arr po funkciji cmp
    sort(arr, arr + n, cmp);

    int curWeight = 0; // Current weight in knapsack
    double finalvalue = 0.0; // Result (value in Knapsack)

    // Prolazak kroz sve članove
    for (int i = 0; i < n; i++)
    {
        // Ako dodavanje još jednog člana neće prekoračiti opseg,
        // dodaj ga celog
        if (curWeight + arr[i].weight <= weight)
        {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }

        // Ako ne možemo dodati ceo član, dodaj njegov deo i izađi iz petlje.
        else
        {
            int remain = weight - curWeight;
            finalvalue += arr[i].value * ((double) remain / arr[i].weight);
            break;
        }
    }

    // Returning final value
    return finalvalue;
}

// driver program to test above function
int main()
{
    int W = 50; // Weight of knapsack
    Item arr[] = {{60, 10}, {100, 20}, {120, 30}};

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Maximum value we can obtain = "
        << fractionalKnapsack(W, arr, n);
    return 0;
}