Cod sursa(job #2803941)

Utilizator acostin643costin andrei acostin643 Data 20 noiembrie 2021 17:27:00
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <algorithm>

using namespace std;

struct obct
{
    int val, g;
    double dens;
};

bool ok(obct a, obct b)
{
    if(a.dens == b.dens)
        return a.g > b.g;
    return a.dens > b.dens;
}

int main()
{
    int n, Gmax, GTot = 0, k = 1;
    double VTot = 0;
    obct obiecte[1005];
    cin >> n >> Gmax;
    for(int i = 1; i <= n; i++)
    {
        cin >> obiecte[i].g >> obiecte[i].val;
        obiecte[i].dens = 1.0 * obiecte[i].val / obiecte[i].g;
    }
    obiecte[n + 1].g = obiecte[n + 1].val = obiecte[n + 1].dens = 0;
    sort(obiecte + 1, obiecte + n + 1, ok);
    while(GTot <= Gmax && k <= n)
    {
        if(GTot + obiecte[k].g <= Gmax)
            GTot += obiecte[k].g, VTot += obiecte[k].val, k++;
        else break;
    }
    VTot += 1.0 * (Gmax - GTot) * obiecte[k].dens;
    cout << VTot;
    return 0;
}