Cod sursa(job #3220145)

Utilizator CraiuAndreiCraiu Andrei David CraiuAndrei Data 2 aprilie 2024 16:52:24
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#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;
}