Pagini recente » Cod sursa (job #607136) | Cod sursa (job #2049182) | Cod sursa (job #722287) | Cod sursa (job #2032329) | Cod sursa (job #2525004)
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
struct s {
double greutate, profit, raport;
int indice;
};
s v[nmax];
int n, g;
void input()
{
fin >> n >> g;
for (int i = 1; i <= n; i++)
{
fin >> v[i].greutate >> v[i].profit;
v[i].raport = v[i].profit / v[i].greutate;
v[i].indice = i;
}
}
bool sortareRaport (s left, s right)
{
return (left.raport > right.raport);
}
int greedy()
{
int i = 1;
int sum = v[i].profit;
int verif = v[i].greutate;
while (verif <= g)
{
i++;
if (verif + v[i].greutate <= g)
{
verif += v[i].greutate;
sum += v[i].profit;
}
else break;
}
if (verif != g && v[i].indice)
{
sum += v[i].profit / (v[i].greutate / (g - verif));
}
return sum;
}
int main()
{
input();
sort(v + 1, v + n + 1, sortareRaport);
fout << greedy();
return 0;
}