/*
 * Das Programm demonstriert 2 Lösungen zum Rucksackproblem
 * über 
 *
 * - Greedy-Algorithmus und
 * - Backtracking.
 *
 * Gegenstände und Rucksäcke werden als Objekte von hier definierten
 * Klassen umgesetzt. Weiterhin verwendet das Programm 
 * Template-Klassen (Schablonen mit Typparametern) aus der STL
 * (Standard Template Library) - in diesem Fall Mengen, Listen und
 * Vektoren zur Aufbewahrung von Gegenständen und Iteratoren zum 
 * Durchlaufen dieser Kollektionen.
 *
 */

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <set>
#include <list>
#include <vector>
using namespace std;

// Anzahl zur Auswahl stehender Gegenstände
#define ANZAHL 18
// max. Gewicht bzw. Nutzen eines Gegenstandes
#define MAX_GEWICHT 100
#define MAX_NUTZEN 100
// Kapazität (maximales Gesamtgewicht) eines Rucksackinhalts
#define KAPAZITAET 100

class Gegenstand {

	public:
		// Der Default-Konstruktor erzeugt einen Gegenestand
		// mit zufälligem Gewicht und Nutzen
		Gegenstand() {
			gewicht = 1+rand()%MAX_GEWICHT;
			nutzen = 1+rand()%MAX_NUTZEN;
		};
		int gewicht;
		int nutzen;
};

// Hilfsfunktion zur Sortierung von Gegenständen nach 
// - Ihrem Nutzen (absteigend) und bei gleichem Nutzen
// - Gewicht (aufsteigend)

bool vergleichsfunktion(Gegenstand* g1, Gegenstand* g2) {
	if (g1->nutzen > g2->nutzen) return true;
	if (g1->nutzen == g2->nutzen && g1->gewicht < g2->gewicht)
			return true;
	return false;
}

// Alternative Hilfsfunktion zur Sortierung von Gegenständen nach 
// dem Verhältnis von Nutzen und Gewicht (absteigend)
// (liefert bei Greedy-Algorithmus die besseren Ergebnisse)

bool vergleichsfunktion2(Gegenstand* g1, Gegenstand* g2) {
	if ((float)g1->nutzen/g1->gewicht > 
		(float)g2->nutzen/g2->gewicht) return true;
	return false;
}

class Rucksack {

	public:
		int gesamtnutzen();
		int gesamtgewicht();
		bool einpacken(Gegenstand*);
		void ausgabe();
	private:
		set<Gegenstand*> inhalt;
};

int Rucksack::gesamtnutzen() {
	int gnutzen = 0;
	set<Gegenstand*>::const_iterator pos;
	for (pos = inhalt.begin(); pos != inhalt.end(); pos++) {
		Gegenstand* g = *pos;
		gnutzen += g->nutzen;
	}
	return gnutzen;
}

int Rucksack::gesamtgewicht() {
	int ggewicht = 0;
	set<Gegenstand*>::const_iterator pos;
	for (pos = inhalt.begin(); pos != inhalt.end(); pos++) {
		Gegenstand* g = *pos;
		ggewicht += g->gewicht;
	}
	return ggewicht;
}

bool Rucksack::einpacken(Gegenstand* g) {
	if (gesamtgewicht() + g->gewicht <= KAPAZITAET) {
		inhalt.insert(g);
		return true;
	}
	return false;
}

void Rucksack::ausgabe() {
	cout << "Rucksack mit folgendem Inhalt:" << endl;
	set<Gegenstand*>::const_iterator pos;
	for (pos = inhalt.begin(); pos != inhalt.end(); pos++) {
		Gegenstand* g = *pos;
		cout << "Gegenstand mit Gewicht " << g->gewicht 
			<< " und Nutzen " << g->nutzen << endl;
	}	
	cout << "Gesamtgewicht: " << gesamtgewicht() << endl;
	cout << "Gesamtnutzen: " << gesamtnutzen() << endl;
}


// Funktion zum Packen eines Rucksacks mit einem
// Greedy-Algorithmus (schnell, liefert aber nicht 
// unbedingt das korrekte Ergebnis - nur lokal optimale
// Entscheidungen)

Rucksack packenGreedy(list<Gegenstand*> auswahl) {

	Rucksack rs;
	// Zuerst sortieren wir (d.h. wir überlassen die Arbeit einer Methode
	// der STL-Klasse list) die zur Auswahl stehenden Gegenstände
	// - mit vergleichsfunktion() nach Nutzen (siehe oben)
	// - mit vergleichsfunktion2() nach Verhältnis Nutzen/Gewicht (siehe oben)
	auswahl.sort(vergleichsfunktion);
	// Dann packen wir die Gegenstände entsprechend dieser Reihenfolge in unseren
	// Rucksack, bis nichts mehr passt
	list<Gegenstand*>::const_iterator pos;
	for (pos = auswahl.begin(); 
			rs.gesamtgewicht() < KAPAZITAET && pos != auswahl.end(); pos++) {
		Gegenstand* g = *pos;
		rs.einpacken(g);
	}
	return rs;
}

// Die rekursive Funktion zum Packen des Rucksacks. Grundprinzip des BAcktracking 
// ist, dass ALLE MÖGLICHEN Rucksäcke gepackt werden. Für jeden Gegenstand an der 
// aktuellen Position (pos) des Vektors mit den Gegenständen (auswahl) wird
// der aktuelle Rucksack (rs) untersucht, ob die oprimale Lösung diesen Gegenstand
// enthält oder nicht.

Rucksack packenRekursiv(Rucksack rs,vector<Gegenstand*>* auswahl, int pos) {
	
	if (pos < auswahl->size() && rs.gesamtgewicht() < KAPAZITAET) {
		// (1) Finde die optimale von rs abgeleitete Lösung, in der
		// der aktuelle Gegenstand NICHT enthalten ist
		Rucksack rs1 = packenRekursiv(rs,auswahl,pos+1);
		// (2) Finde die optimale von rs abgeleitete Lösung, in der
		// der aktuelle Gegenstand enthalten ist
		rs.einpacken((*auswahl)[pos]);
		Rucksack rs2 = packenRekursiv(rs,auswahl,pos+1);
		// Gib die bessere von beiden Lösungen als Ergebnis zurück
		if (rs1.gesamtnutzen() > rs2.gesamtnutzen()) return rs1;
		return rs2;
	}
	return rs;
}

// Dies ist der Rekursionseinstieg für das Packen eines Rucksacks
// über Backtracking, da die rekursive Funktion andere Parameter
// benötigt (siehe oben).

Rucksack packenBacktracking(list<Gegenstand*> auswahl) {

	vector<Gegenstand*>* v = new vector<Gegenstand*>(auswahl.begin(),auswahl.end());
	Rucksack rs;
	rs = packenRekursiv(rs,v,0);
	return rs;
}

int main() {

	// Initialisierung des Zufallszahlengenerators
	srand(time(NULL));
	// Erzeugung einer Liste mit zufälligen Gegenständen
	// (siehe Gegenstand-Konstruktor)
	list<Gegenstand*> auswahl;
	for (int i=0; i<ANZAHL; i++)
		auswahl.push_back(new Gegenstand());

	// Erster Versuch: packen des Rucksacks mit 
	Rucksack r1 = packenGreedy(auswahl);
	cout << "Ergebnis von Greedy:" << endl; 
	r1.ausgabe();
	Rucksack r2 = packenBacktracking(auswahl);
	cout << "Ergebnis von Backtracking:" << endl; 
	r2.ausgabe();
}