Cod sursa(job #2773276)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 6 septembrie 2021 08:21:15
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <algorithm>
#include <cmath>

struct obiect{
    int greutate, valoare;
};

int n, Gmax;
obiect O[5001];
std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");

bool fcmp(obiect A, obiect B)
{
    return A.valoare * B.greutate > A.greutate * B.valoare;
}

int main(){
    fin >> n >> Gmax;
    for(int i=1 ; i<=n ; ++i)
        fin >> O[i].greutate >> O[i].valoare;
    std::sort(O + 1 , O + n + 1, fcmp);
    int G = 0;
    double V = 0;
    int i = 1;
    while( i <= n)
    {
        if(G + O[i].greutate <= Gmax)
        {
            G += O[i].greutate;
            V += O[i].valoare;
            i ++;
        }
        else
        if(Gmax - G > 0)
        {
            int x = Gmax - G;
            double factor = 1.0 * x / O[i].greutate;
            G = Gmax;
            V += factor * O[i].valoare;
            i++;
        }
        else
            i = n + 1;
    }
    fout << floor(V);
    return 0;
}