Cod sursa(job #2083218)

Utilizator Andrei_Info1Ionescu Andrei Andrei_Info1 Data 7 decembrie 2017 11:52:29
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct OB
{
    int g, v;
    double f;
}o[1005];
bool cmp(OB a, OB b)
{
    if(a.f>b.f)
        return 1;
    return 0;
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int i, n, gmax, pf=0;

    scanf("%d%d", &n, &gmax);
    for(i=0 ; i<n ; i++)
    {
        scanf("%d%d", &o[i].g, &o[i].v);
        o[i].f=(float)o[i].v/o[i].g;
    }
    sort(o, o+n, cmp);
    for(i=0 ; i<n && (gmax-o[i].g >= 0) ; i++)
        pf+=o[i].v, gmax-=o[i].g;
    if(gmax && i<n)
        printf("%.3lf", pf+gmax*o[i].f);
    else
        printf("%d", pf);
    return 0;
}