Cod sursa(job #2509665)

Utilizator TheVigilante39Daniel Iova TheVigilante39 Data 14 decembrie 2019 15:06:19
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

struct obj{
    int g, c;
    double r = 0.0;

}a[5001];

bool cmp(obj a, obj b){
    return a.r > b.r;
}

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

int main(){

    int n, w;
    fin >> n >> w;
    for (int i = 0; i < n; i++){
        fin >> a[i].g >> a[i].c;
        a[i].r = (double)a[i].c/a[i].g;
    }
    sort(a, a+n, cmp);
    int greutate_curenta = 0;
    int s = 0;
    for (int i = 0; i < n; i++){
        if (greutate_curenta + a[i].g <= w){
            greutate_curenta += a[i].g;
            s += a[i].c;
        }
        else {
            int ok = w - greutate_curenta;
            s += a[i].c*((double)ok/a[i].g);
            break;
        }
    }
    fout << s << endl;

}