Cod sursa(job #1579773)

Utilizator cicero23catalin viorel cicero23 Data 25 ianuarie 2016 08:27:05
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct ob
{
    float pret,kg;
};
int comp(ob a,ob b)
{
    return (a.pret/a.kg>b.pret/b.kg);
}
int n,G,i,s;
ob v[5001];
int main()
{
    f>>n>>G;
    for(i=1;i<=n;i++)
    {
        f>>v[i].kg;
        f>>v[i].pret;
    }
    sort(v+1,v+n+1,comp);
    s=0;
    for(i=1;i<=n&&G>0;i++)
    {
        if(v[i].kg<=G){s+=v[i].pret;G-=v[i].kg;}
        else break;
    }
    g<<s;
    return 0;
}