Cod sursa(job #3210303)

Utilizator CRazvaN6Cutuliga Razvan CRazvaN6 Data 5 martie 2024 21:33:21
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#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;
}