Pagini recente » Cod sursa (job #313918) | Cod sursa (job #333066) | Cod sursa (job #2279558) | Cod sursa (job #2007606) | Cod sursa (job #3154757)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
struct obiect
{
int g, v;
double profit;
}obj[5005];
bool verif(obiect x, obiect y)
{
return (x.profit > y.profit);
}
int main()
{
int n, gmax;
cin >> n >> gmax;
for (int i = 1; i <= n; ++i)
{
cin >> obj[i].g >> obj[i].v;
obj[i].profit = 1.0 * obj[i].v / obj[i].g;
}
sort(obj + 1, obj + n + 1, verif);
/*
cout << '\n';
for (int i = 1; i <= n; ++i)
cout << obj[i].g << ' ' << obj[i].v << ' ' << obj[i].profit << '\n';
*/
int i = 1, s = 0;
while(gmax >= obj[i].g && i <= n)
{
gmax -= obj[i].g;
s += obj[i].v;
i++;
}
if (gmax && i <= n)
s += obj[i].profit * gmax;
cout << s;
return 0;
}