Cod sursa(job #1600709)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 15 februarie 2016 12:34:51
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <vector>
using namespace std;
struct obiect{
double g, v, vu;
}x;

int N, Gmax, G, V, a, b;

vector<obiect>v;

bool comp(obiect x, obiect y){
    return x.vu>y.vu;
}

int main()
{
    freopen("rucsac.in", "rt", stdin);
    freopen("rucsac.out", "wt", stdout);
    scanf("%d%d", &N, &Gmax);
    v.assign(N+1, x);
    for(int i=1; i<=N; i++){
        scanf("%d%d", &a, &b);
        v[i].g = a;
        v[i].v = b;
        v[i].vu = v[i].v / v[i].g;
    }
    sort(v.begin()+1, v.end(), comp);
    int o=1;
    while(G + v[o].g <= Gmax && o<=N){
        G += v[o].g;
        V += v[o++].v;
    }
    cout<<V<<'\n';

}