Cod sursa(job #1874858)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 10 februarie 2017 15:01:47
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct obiect {int G, V, P;} v[5001];
int n, GMax, i, C;

void citire() {
  f>>n>>GMax;
  for(i = 1; i <= n; ++i) {
    f>>v[i].G>>v[i].V;
    v[i].P=v[i].V/v[i].G;
  }
}

bool greater_value(obiect a, obiect b) {
  return a.P > b.P;
}

void calcul_castig() {
  for(i = 1; i <= n && GMax>0; ++i) {
    if(v[i].G<=GMax) {
      C+=v[i].V;
      GMax-=v[i].G;
    } else {
      C+=v[i].P*GMax;
      GMax=0;
    }
  }
}

int main()
{
  citire();
  sort(v+1, v+n+1, greater_value);
  calcul_castig();
  g<<C;
  return 0;
}