Cod sursa(job #2579571)

Utilizator BOGDABogdan BOGDA Data 12 martie 2020 16:58:55
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

struct Obiect {
	float G, V;
};

bool cdt(Obiect A, Obiect B)
{
	return (A.V / A.G) > (B.V / B.G);
}

int main()
{
	Obiect v[1001];
	int n, i, Gmax;
	float P = 0;

	fin >> n >> Gmax;
	for (i = 1; i <= n; i++) cin >> v[i].G >> v[i].V;

	sort(v + 1, v + n + 1, cdt);

	i = 1;
	while (Gmax >= 0 && i <= n)
	{
		if (Gmax - v[i].G >= 0)
		{
			Gmax -= v[i].G;
			P += v[i].V;
		}
		else if (Gmax != 0)
		{
			P += ((Gmax * v[i].V) / v[i].G);
			Gmax = 0;
		}
		i++;
	}
	fout << P;

	return 0;
}