Kurs:Algorithmen und Datenstrukturen/Vorlesung/Beispiel:Rucksackproblem Greedy

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Das Rucksackproblem als Greedy Algorithmus

Nun wird das Rucksackproblem mit dem Greedy Algorithmus gelöst. Wir erinnern uns, das Greedy-Grundprinzip ist es in jedem Berechnungsschritt die jeweils aktuell geeignetste Zwischenlösung zu verwenden. Angewandt auf unser Rucksackproblem bedeutet das, lege von den noch nicht im Rucksack befindlichen Gegenständen jeweils den „besten“ hinzu. Doch was ist der beste Gegenstand? Der nützlichste? Der leichteste? Der mit dem besten Verhältnis aus Nutzen und Gewicht?

Algorithmus nach Nutzen

static Rucksack packeGierigNachNutzen() {
	Rucksack r = new Rucksack();
	while (true) {
		int pos=-1; int besterNutzen = 0;
		for (int i=0; i<auswahlObjekte.length; i++)
			if (r.auswahl[i] == false &&
				auswahlObjekte[i].nutzen > besterNutzen &&
				r.gewicht() + auswahlObjekte[i].gewicht <= 
					kapazitaet) {
			   besterNutzen = auswahlObjekte[i].nutzen;
			   pos = i;
			}
		if (pos == -1) break;
		else r.auswahl[pos] = true;
	}
	return r;
}

Algorithmus nach Gewicht

static Rucksack packeGierigNachGewicht() {
	Rucksack r = new Rucksack();
	while (true) {
		int pos=-1; int bestesGewicht = MAX_GEWICHT+1;
		for (int i=0; i<auswahlObjekte.length; i++)
			if (r.auswahl[i] == false &&
				auswahlObjekte[i].gewicht < bestesGewicht &&
				r.gewicht() + auswahlObjekte[i].gewicht <= 
					kapazitaet) {
			   bestesGewicht = auswahlObjekte[i].gewicht;
			   pos = i;
			}
		if (pos == -1) break;
		else r.auswahl[pos] = true;
	}
	return r;
}

Aufruf in main()

public static void main (String args[]) {
	if (args.length == 1)
		anzahlObjekte = Integer.parseInt(args[0]);
	kapazitaet = (int) (anzahlObjekte * MAX_GEWICHT / 4);
	auswahlObjekte = erzeugeObjekte();

	Rucksack r1 = packeGierigNachGewicht();
	System.out.println(„Greedy Gewicht: „ + r1);

	Rucksack r2 = packeGierigNachNutzen();
	System.out.println(„Greedy Nutzen: „ + r2);
	…

Analyse

Der Vorteil ist der relativ geringe Berechnungsaufwand durch die quadratische Komplexität $O(n^{2})$. Das Problem ist aber, dass nicht die optimale Lösung gefunden wird.