Pagini recente » Cod sursa (job #1903086) | Cod sursa (job #1093290) | Cod sursa (job #2378820) | tema | Cod sursa (job #3234627)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, gm;
int castig = 0;
struct obiect
{
int g,v;
float c;
} o[20000];
void citire()
{
int i;
fin >> n >> gm;
for(i = 1; i <= n; i++)
{
fin >> o[i].g >> o[i].v;
o[i].c = (float)o[i].v / o[i].g;
}
}
void sortare()
{
int i, j;
for(i = 1; i < n; i++)
for(j = i + 1; j <= n; j++)
if(o[i].c < o[j].c)
swap(o[i], o[j]);
}
int alegere()
{
int i;
for(i = 1; i <= n && gm != 0; i++)
{
if(o[i].g <= gm)
{
gm -= o[i].g;
castig += o[i].v;
}
else
{
castig += o[i].c * gm;
gm = 0;
}
}
return castig;
}
int main()
{
citire();
sortare();
fout << alegere() << "\n";
fin.close();
fout.close();
return 0;
}