Cod sursa(job #2589691)

Utilizator MohamedXXXhaide sarpili MohamedXXX Data 26 martie 2020 18:32:20
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

struct ob {
    double g, valoare, e;
} obj[5001];

int n;
double mw;

bool comp(ob a, ob b) {
    return a.e > b.e;
}

int main()
{
    in >> n >> mw;
    for(int i = 1; i <= n; i++) {
        in >> obj[i].g >> obj[i].valoare;
        obj[i].e = obj[i].valoare / obj[i].g;
    }

    sort(obj + 1, obj + 1 + n, comp);

    long double t = 0;
    for(int i = 1; i <= n && mw > 0; i++) {
        if(mw - objects[i].g >= 0) {
            t += objects[i].valoare;
        } else {
            t += mw * objects[i].valoare / objects[i].g;
        }
        mw -= objects[i].g;
    }
    out << (int)t;
    return 0;
}