Knapsack.cpp

#include<iostream>
#include<algorithm>
#include <cmath>
#include <limits>
#include <iomanip>

using namespace std;

struct Item{
    double value;
    double weight;
    double density;
};

int main()
{
    int n,c; // c for Capacity
    cin >> n >> c;
    Item items[n];
    double v = 0,
        w = 0;
    
    for(unsigned int i =0; i < n;i++){
    
        cin >> v >> w;
        Item tmp = { v , w , v/w };
        items[i] = tmp;
    }
    
    // sort items per density
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(items[i].density > items[j].density){
                Item tmp = items[i];
                items[i] = items[j];
                items[j] = tmp;
            }
        }
    }
    
    double benifit = 0;
    int totalWeight = 0;
    
    for(int i = 0; i < n; i++){
        Item item = items[i];
        int weight = item.weight + totalWeight;
        if(weight <= c)
        {
            totalWeight = weight;
            benifit += item.value;
        } else {
            benifit += (c - totalWeight)/item.weight * item.value;
            totalWeight = c;
        }
    }
    cout << std::fixed << std::setprecision(4) << benifit << "\n";
    
    
    
    return 0;
}