EntwurfRZ

Aus ProgrammingWiki

Archivierte Version vom 2016-01-20T18:09:59+00:00. Aktuelle Version

Pseudopolynomialität

Das Rucksackproblem scheint auf den ersten Blick mit dynamischer Programmierung in Polynomialzeit lösbar zu sein.
Im folgenden Beispielcode gibt es:

Eine for-Schleife zur Initialisierung des Array \mathcal{O}(n+1) (vernachlässigbar, da es eine Eigenart von Javascript ist, dass man mehrdimensionale Arrays nicht mit einem einzigen Aufruf erzeugen kann)
Eine äußere for-Schleife über die Anzahl der Gegenstände \mathcal{O}(n)
Eine innere for-Schleife über Anzahl der möglichen Gewichte \mathcal{O}(max)

Es ergibt sich damit eine Laufzeit von \mathcal{O}(n) \dot{} \mathcal{O}(max) = \mathcal{O}(n \dot{} max), was zunächst polynomial erscheint.

function knapsack(max, objects){
	var n = objects.length; // Anzahl der Gegenstände
	// Initialisierung der Ergebnismatrix (Opt-Gewichte bei Verwendung von i Gegenständen und Maximalgewicht j)
	var R = Array(n+1); // Mögliche Anzahl von Gegenständen (+1 für 0 Gegenstände)
	for(var i = 0; i < n+1; i++)
		R[i] = Array.apply(null, Array(max+1)).map(Number.prototype.valueOf,0); // Mögliche Gewichte (+1 da inkl. 0)
	// Iteration über Gegenstände und mögliche Zwischengewichte
	for(var i = 0; i < n; i++){ // Für jeden Gegenstand
		for(var j = 1; j <= max; j++){ // Für jedes mögliche Zwischengewicht
			if (objects[i].w <= j){ // Gegenstand leichter oder gleich max
				var wSum = objects[i].v + R[i][j-objects[i].w]; // Gewicht-Summe von Gegenstand und möglicher Rest-Füllung
				R[i+1][j] = Math.max(wSum, R[i][j]); // Summe oder besser ohne diesen Gegenstand
			}
			else // Gegenstand zu schwer
				R[i+1][j] = R[i][j]; // Gewicht ohne diesen Gegenstand übernehmen
		}
	}
	return R[objects.length][max];
}

knapsack(120,[{w:13,v:19},{w:11,v:20},{w:17,v:23},{w:15,v:21},{w:16,v:27},{w:14,v:25},{w:18,v:25},{w:10,v:18},{w:19,v:24},{w:12,v:17}]);

Der Irrtum liegt in der Betrachtung von max als Konstante. Bei der Worst-Case-Betrachtung kann max jeden beliebigen Wert annehmen. Somit kann man ihn auch in Abhängigkeit von n definiert, z.B. max = 2^n
Es ergibt sich damit eine Komplexität von \mathcal{O}(n \dot{} 2^n) welche nicht mehr polynomial begrenzt ist.

EntwurfRZ

Pseudopolynomialität

Suche