Cod sursa(job #1985286)

Utilizator ioana.jianuIoana Jianu ioana.jianu Data 27 mai 2017 13:34:04
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct capacitate {
  int g, p;
};

bool comparare ( capacitate a, capacitate b ) {
  if ( a.p * b.g > a.g * b.p )
    return true;
  else
    return false;
}

capacitate v[10001];

int main() {
  FILE *fin, *fout;
  int n, greutate, i, s = 0,  ok;
  float profit = 0, y = 0;

  fin = fopen ( "rucsac.in", "r" );
  fout = fopen ( "rucsac.out", "w" );
  fscanf ( fin, "%d%d", &n, &greutate );
  for ( i = 1; i <= n; i++ )
    fscanf ( fin, "%d%d", &v[i].g, &v[i].p );
  sort ( v+1, v+n+1, comparare );
  i = 1;
  ok = 0;
  while ( i <= n && ok == 0 ) {
    if ( s + v[i].g <= greutate ) {
      s+=v[i].g;
      profit+=v[i].p;
    }
    else {
      y = (( greutate - s ) *1.0/ v[i].g ) * v[i].p ;
      s = greutate;
      profit += y;
      ok=1;
    }

    i++;
  }
  fprintf ( fout, "%.1f", profit );
  fclose(fin);
  fclose(fout);
  return 0;
}