EntwurfRZ

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
==Pseudopolynomialität==
Das Rucksackproblem scheint auf den ersten Blick mit dynamischer Programmierung in Polynomialzeit lösbar zu sein.<br>
<code id="569fbc4c51049">
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++) // Pro Gegenstandsanzahl
		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];
}
</code>
<run id="569fbc4c51103">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}]);</run>
Bei Betrachtung der Implementation findet man:
* 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.

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$ definieren, z.B. $max = 2^n$<br>
Es ergibt sich damit eine Komplexität von $\mathcal{O}(n \dot{} 2^n)$ welche nicht mehr polynomial begrenzt ist.