Pagini recente » Cod sursa (job #2038030) | Cod sursa (job #461467) | Cod sursa (job #269828) | Cod sursa (job #2455502) | Cod sursa (job #2051779)
#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gmax;
float cmax;
struct ob {
int o,g;
float c;
}v[1015];
int comp(ob x,ob y) {
return x.c/x.g>y.c/y.g;
}
void sol() {
int i;
float p;
for (i=1;i<=n && gmax!=0;i++)
if (v[i].g<=gmax) {
gmax-=v[i].g;
cmax+=v[i].c;
//cout<<v[i].o<<' '<<1<<'\n';
}
else {
p=(float)gmax/v[i].g;
gmax=0;
cmax+=v[i].c*p;
//cout<<v[i].o<<' '<<v[i].c*p<<'\n';;
}
g<<(int)cmax;
}
int main() {
int i;
f>>n>>gmax;
for (i=1;i<=n;i++) {
f>>v[i].g>>v[i].c;
v[i].o=i;
}
sort(v+1,v+n+1,comp);
//cout<<'\n';
/*for (i=1;i<=n;i++)
cout<<v[i].g<<' '<<v[i].c<<'\n';
*/sol();
return 0;
}