Pagini recente » Cod sursa (job #806624) | Cod sursa (job #268108) | Cod sursa (job #2227842) | Cod sursa (job #1122573) | Cod sursa (job #3210303)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm> // Adaugă biblioteca algorithm pentru sortare
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, gMax;
int ans;
struct Object {
int weight;
int value;
double ratio;
};
bool compareObjects(const Object &a, const Object &b) {
return a.ratio > b.ratio;
}
int main() {
f >> n >> gMax;
vector<Object> objects(n);
vector<int> T(gMax + 1, 0);
for(int i = 0; i < n; ++i){
f >> objects[i].weight >> objects[i].value;
objects[i].ratio = (double)objects[i].value / objects[i].weight;
}
sort(objects.begin(), objects.end(), compareObjects);
for(int i = 0; i < n; ++i){
if(gMax >= objects[i].weight) ans += objects[i].value, gMax -= objects[i].weight;
else ans += objects[i].value * ((double) gMax / objects[i].weight);
}
g << ans;
return 0;
}