Cod sursa(job #3154757)

Utilizator VladLuncanLuncan Vlad VladLuncan Data 5 octombrie 2023 23:05:24
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

struct obiect
{
    int g, v;
    double profit;
}obj[5005];

bool verif(obiect x, obiect y)
{
    return (x.profit > y.profit);
}

int main()
{
    int n, gmax;

    cin >> n >> gmax;
    for (int i = 1; i <= n; ++i)
    {
        cin >> obj[i].g >> obj[i].v;
        obj[i].profit = 1.0 * obj[i].v / obj[i].g;
    }

    sort(obj + 1, obj + n + 1, verif);
   
    /*
    cout << '\n';
    for (int i = 1; i <= n; ++i)
        cout << obj[i].g << ' ' << obj[i].v << ' ' << obj[i].profit << '\n';
    */

    int i = 1, s = 0;
    while(gmax >= obj[i].g && i <= n)
    {
        gmax -= obj[i].g;
        s += obj[i].v;
        i++;
    }
    if (gmax && i <= n)
        s += obj[i].profit * gmax;

    cout << s;

    return 0;
}