Pagini recente » Cod sursa (job #2315778) | Cod sursa (job #2154452) | Cod sursa (job #92896) | Cod sursa (job #2421452) | Cod sursa (job #2109811)
#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;
}