Pagini recente » Monitorul de evaluare | Cod sursa (job #3280334) | Monitorul de evaluare | Statistici Stoenica Mihai (mihai_stoenica) | Cod sursa (job #3220145)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G;
int Max;
struct Obiect {
int greutate, valoare;
bool operator<(const Obiect E) const
{
return valoare * E.greutate > greutate * E.valoare;
}
}a[5005];
int main()
{
int i;
fin >> n >> G;
for (i = 1; i <= n; i++)
fin >> a[i].greutate >> a[i].valoare;
sort(a + 1, a + 1 + n);
for (i = 1; i <= n && G > 0; i++)
{
if (a[i].greutate <= G)
{
G -= a[i].greutate;
Max += a[i].valoare;
}
else
{
Max += (G * a[i].valoare / a[i].greutate);
G = 0;
}
}
fout << Max;
return 0;
}