Pagini recente » Cod sursa (job #1922294) | Cod sursa (job #2059203) | Cod sursa (job #1517558) | Cod sursa (job #291191) | Cod sursa (job #2682877)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define dim 6000005
using namespace std;
struct rucsac
{
int greutate;
int profit;
};
rucsac elem[10001];
bool cmp(rucsac e1, rucsac e2) {
return (float) e1.profit/e1.greutate > (float) e2.profit/e2.greutate;
}
int main()
{
freopen("rucsacfr.in", "r", stdin);
freopen("rucsacfr.out", "w", stdout);
int numar,capacitate,i;
cin>>numar>>capacitate;
for(i=0;i<numar;i++)
{
cin>>elem[i].greutate>>elem[i].profit;
}
sort(elem, elem + numar, cmp);
/*for (i = 0; i < numar; i++) {
out << elem[i].greutate << " " << elem[i].profit << '\n';
}*/
int maxi=0, idx = 0;
float rezultat=0;
while(capacitate != maxi)
{
if (elem[idx].greutate + maxi <= capacitate) {
// iau tot obiectul
rezultat += elem[idx].profit;
maxi += elem[idx].greutate;
} else {
// trebuie sa iau o fractiune din obiectul curent
rezultat += (capacitate - maxi) * (float)elem[idx].profit/elem[idx].greutate;
maxi = capacitate;
}
idx++;
// cout << rezultat << "\n";
}
cout<<rezultat;
return 0;
}