/************************************************
Algorithmen und Problemloesungen mit C++,
http://www.algorithmen-und-problemloesungen.de
Copyright @2007 by Doina Logofatu
************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef struct{
  float g, v;
  int idx;
} TObject;

void readData(TObject *a, int *n, float *M){ 
  FILE *fin = fopen("objects.in", "r");
  float g, v;
  *n=0;
  if(fin) fscanf(fin, "%f", M);
  while(fin && fscanf(fin, "%f%", &g) == 1){
    fscanf(fin, "%f%", &v);
    a[*n].g   = g;
    a[*n].v   = v;
    a[*n].idx = *n;
    (*n)++;
  }
}

int compare(const void *a, const void *b){
  TObject *o1 = (TObject*) a;
  TObject *o2 = (TObject*) b;
  return ((o2->v/o2->g - o1->v/o1->g)>0);
}

int main(){
  int n, i, j;  
  TObject a[50];
  float M;
  FILE *fout;
  fout = fopen("rucksack.out", "w");
  readData(a, &n, &M);
  qsort((void*)a, n, sizeof(TObject), compare);
  i=0;
  while(M>0){
    if(M>=a[i].g){
      M -= a[i].g;
      i++;
    } else {
        M = -M;
    }
  }
  for(j=0; j<i; j++){
    fprintf(fout, "Objekt %2d: %4.2f %4.2f - vollstaendig\n", 
      a[j].idx+1, a[j].g, a[j].v);      
  }
  if(M<0){
    fprintf(fout, "Objekt %2d: %4.2f %4.2f - %4.2fkg\n", 
      a[i].idx+1, a[i].g, a[i].v, -M);
  }
  return 0;  
}