bwi-challenge

Installation und Ausführung

Nachdem das Repository geclont wurde, kann das Progamm wie folgt kompiliert werden:
mkdir out
javac -d out/ src/*.java

Wenn erfolgreich kompiliert wurde, kann das Programm wie folgt ausgeführt werden:
java -Xmx3072m -cp out Main

Alternativ kann auch die .jar Datei hier heruntergeladen und entsprechend den Anweisungen auf der Seite ausgeführt werden.

Anmerkung: Zur Ausführung werden mind. 3GB freien Arbeitsspeichers benötigt. Das flag -Xmx3072m reserviert eben diese 3GB für die Anwendung. Es hat auch schon mit weniger geklappt (z.B. -Xmx2048m), jedoch würde ich - sofern möglich - bei den 3GB bleiben. Ansonsten droht evtl. ein OutOfMemoryError.

Wahl des Algorithmus

Das Problem ist eine leichte Abwandlung eines "Multiple Knapsack Problems".
Die exakte Lösung hierzu zu berechnen ist mit einer solchen Anzahl an items nicht (in vernünfitger Zeit) möglich.
Deswegen wird das Problem hier in "einfache Knapsack Probleme" unterteilt, die mit einer Abwandlung des allgemeinen Lösungsansatzes gelöst werden.
Das Ergebnis ist eine Approximation des exakten Ergebnisses. Der hier entstandene Fehler dürfte
jedoch aufgrund der geringen Anzahl der "Knapsacks" (zwei) nicht allzu stark ins Gewicht fallen.

Optimale Verteilung

Anmerkung: Das Gesamtgewicht ist in Gramm gegeben