// Rucksack packen, Optimierung mit Sortieren und Restgewicht
// Gegenstände aus einer Datei lesen
//
// Aufruf: rucksack Maximalgewicht Materialfile
//
// Klaus Kusche, 2013

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

// max. Anzahl der Gegenstände
#define MAX 100

// Typ für die Daten eines Gegenstandes
typedef struct {
  char name[32];             // Bei Längenänderung: fscanf-Format anpassen!
  double gewicht;
  double wert;
  // Die Member akt_dabei (für die aktuelle Lösung)
  // und opt_dabei (für die optimale Lösung) zeigen an,
  // ob der Gegenstand eingepackt wird:
  // false ... Gegenstand i bleibt heraußen
  // true  ... Gegenstand i kommt in den Rucksack
  bool akt_dabei;
  bool opt_dabei;
  double faktor;             // Wert / Gewicht, für die Optimierung
} gegenstand;

gegenstand liste[MAX];       // Daten aller Gegenstände
int anzahl = 0;              // tatsächliche Anzahl der Gegenstände in liste

// Wert der bisher besten Lösung (Summe aller Gegenstände mit opt_dabei)
double opt_wert = 0;

int aufruf = 0;              // Aufruf-Zähler

int vergleich(const void *p1, const void *p2);
void lsg(double wert);
void probier(int i, double platz, double wert);

// Die Vergleichsfunktion für qsort:
// Sortierung der Strukturen im Array nach dem member faktor
// Elemente mit *kleinerem* Wert pro Gewicht gehören
// beim Sortieren im Array nach *hinten*, sind also sortiermäßig *größer*!
int vergleich(const void *p1, const void *p2)
{
  const gegenstand *a = (const gegenstand *)p1;
  const gegenstand *b = (const gegenstand *)p2;

  if (a->faktor < b->faktor) {
    return 1;
  }
  if (a->faktor > b->faktor) {
    return -1;
  }
  return 0;
}

// akt_dabei enthält eine fertige Lösung, "wert" ist ihr gesamter Wert.
// Wenn sie besser ist als die bisher beste Lösung, 
// dann kopiere sie nach opt_dabei und merk dir den neuen optimalen Wert.
void lsg(double wert)
{
  if (wert > opt_wert) {
    for (int i = 0; i < anzahl; ++i) {
      liste[i].opt_dabei = liste[i].akt_dabei;
    }
    opt_wert = wert;
  }
}

// Probiere den Gegenstand Nummer i
// platz ist der noch freie Platz im Rucksack
// wert ist der bisherige Wert des Rucksacks
void probier(int i, double platz, double wert)
{
  ++aufruf;
  if (i == anzahl) {
    // kein Gegenstand mehr zur Wahl ==> Lösung ist fertig!
    lsg(wert);
    return;
  }
  
  gegenstand *g = &(liste[i]);   // Zeiger auf Gegenstand Nummer i
  
  // Optimierung:
  // Alle noch vorhandenen Gegenstände haben wegen der Sortierung
  // kleinergleich g->faktor Wert pro Gewicht.
  // Selbst wenn sie den noch vorhandenen Platz restlos füllen,
  // ist ihr Gesamtwert daher sicher kleinergleich (platz * g->faktor).
  // Wenn das in Summe weniger als die beste bekannte Lösung ist,
  // kann die aktuelle Lösung keine optimale mehr werden.
  if (wert + platz * g->faktor <= opt_wert) {
    return;
  }

  if (g->gewicht <= platz) {
    // Gegenstand hat noch Platz ==> probiere es mit ihm
    g->akt_dabei = true;
    probier(i + 1, platz - g->gewicht, wert + g->wert);
  }
  
  // probiere es in jedem Fall ohne den Gegenstand
  g->akt_dabei = false;
  probier(i + 1, platz, wert);
}

int main(int argc, const char *argv[])
{
  double platz;                 // Eingabe: Maximalgewicht des Rucksacks
  if ((argc != 3) || ((platz = atof(argv[1])) <= 0)) {
    fprintf(stderr, "Usage: %s max_gewicht filename\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  
  /*** File einlesen ***/
  FILE *f = fopen(argv[2], "r");
  if (f == NULL) {
    fprintf(stderr, "%s: Can't open %s: %s\n", argv[0], argv[2],
            strerror(errno));
    exit(EXIT_FAILURE);
  }
  int n;  
  while ((n = fscanf(f, "%31s %lf %lf", liste[anzahl].name,
                     &(liste[anzahl].gewicht), &(liste[anzahl].wert))) != EOF) {
    if (n != 3) {  // n ist die Anzahl der erfolgreich gelesenen Werte
      fprintf(stderr, "%s: illegal input on %s\n", argv[0], argv[2]);
      exit(EXIT_FAILURE);
    }
    // sollte nicht nötig sein, aber sicher ist sicher...
    liste[anzahl].akt_dabei = liste[anzahl].opt_dabei = false;
    // faktor gleich berechnen, spart eine eigene Schleife
    liste[anzahl].faktor = liste[anzahl].wert / liste[anzahl].gewicht;
    if (++anzahl == MAX) {
      fprintf(stderr, "%s: More than %d items on %s\n", argv[0], MAX, argv[2]);
      exit(EXIT_FAILURE);
    }
  }
  
  if (ferror(f)) {
    fprintf(stderr, "%s: Can't read %s: %s\n", argv[0], argv[2],
            strerror(errno));
    exit(EXIT_FAILURE);
  }
  if (fclose(f) != 0) {
    fprintf(stderr, "%s: Can't close %s: %s\n", argv[0], argv[2],
            strerror(errno));
    exit(EXIT_FAILURE);
  }
  
  /*** Sortierung ***/
  qsort(liste, anzahl, sizeof(gegenstand), vergleich);

  /*** Berechnung ***/
  probier(0, platz, 0);

  /*** Ausgabe ***/
  double ges_gew = 0; // Gesamtgewicht der Lösung
  for (int i = 0; i < anzahl; ++i) {
    if (liste[i].opt_dabei) {
      printf("%-31s: Gewicht %9.2f, Wert %9.2f\n", liste[i].name,
             liste[i].gewicht, liste[i].wert);
      ges_gew += liste[i].gewicht;
    }
  }
  printf("%-31s: Gewicht %9.2f, Wert %9.2f\n", "Summe", ges_gew, opt_wert);
  printf("Anzahl der Aufrufe: %d\n", aufruf);
  
  exit(EXIT_SUCCESS);
}