Cod sursa(job #2109811)

Utilizator mark2005Mark Erena mark2005 Data 20 ianuarie 2018 10:22:15
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
struct valoare
    {
        double g,v,vpg;
    };
bool cmd(valoare a, valoare b)
{
    if(a.vpg > b.vpg)
        return 1;
    else
        return 0;
}
int main()
{
    int n,i,s=0,sv=0,ok=1,r,l;
    double gmax,w;
    valoare ve[10001];
    in>>n>>gmax;
    for(i=1;i<=n;i++){
        in>>ve[i].g>>ve[i].v;
        ve[i].vpg=ve[i].v/ve[i].g;
    }
    sort(ve+1,ve+n+1,cmd);
    for(i=1;i<=n && ok==1;i++)
    {
        if(s+ve[i].g<=gmax)
        {
            s=s+ve[i].g;
            sv=sv+ve[i].v;
        }
        else{
            ok=0;
            l=i;
        }
    }
    if(s-gmax<-0.01)
    {
        r=gmax-s;
        w=ve[l].g/r;
        sv=sv+ve[l].v/w;
    }
    out<<sv;
    return 0;
}