Cod sursa(job #2773271)

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

 struct obiect
{
    int index;
    int pret;
    int greutate;

    bool operator<(const obiect& other) const
    {
        return ((float)pret / (float)greutate) > ((float)other.pret / (float)other.greutate);
    }
};

obiect v[1001];
int gMax, gCurent, s;
uint32_t i, n;
std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");

int main()
{
    fin >> n >> gMax;
    for (uint32_t i = 0; i < n; i++)
    {
        v[i].index = i+1;
        fin >> v[i].greutate >> v[i].pret;
    }

    std::sort(v + 0, v + n);


    while ((gCurent<=gMax) && (i < n))
    {
        if (v[i].greutate + gCurent <= gMax)
        {
            gCurent += v[i].greutate;
            s += v[i].pret;
        }
        else
        {
            float f = ((float)(gMax) - (float)gCurent) / (float)v[i].greutate;
            gCurent += v[i].greutate * f;
            s += v[i].pret * f;
        }

        i++;
    }

    fout << floor(s);
    return 0;
}