Cod sursa(job #2605011)

Utilizator MattiaMattia Iojica Mattia Data 24 aprilie 2020 11:18:40
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n, GMax;
float sum;

struct obiecte{
    float g, val, ef;
};

obiecte v[5005];

int compara(obiecte x, obiecte y)
{
    return x.ef > y.ef;
}

int main()
{
    f >> n >> GMax;

    for(int i = 1; i <= n; i++)
    {
        f >> v[i].g >> v[i].val;
        v[i].ef = v[i].val / v[i].g;
    }

    sort(v + 1, v + n + 1, compara);


    int i = 1;

    if(v[i].g > GMax)
        sum = 0;
    else
        while(i <= n && GMax > 0)
        {
            if(GMax - v[i].g >= 0)
                sum += v[i].val;
            else
                sum = sum + GMax * v[i].val / v[i].g;

            GMax -= v[i].g;
            i++;
        }

    g << (int)sum;

    return 0;
}