Cod sursa(job #2773269)

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

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

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

obiect v[1001];
float 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 << s;
    return 0;
}