Algorithmen und Datenstrukturen · Senior · Frage 24 von 75
Was bedeutet es, dass die DP für das 0/1-Rucksackproblem pseudopolynomiell ist?
- 1O(n × W) hängt vom Wert W ab, der in seiner Bitlänge exponentiell ist
- 2Sie ist nur polynomiell, wenn alle Gewichte gleich sind
- 3Sie findet immer eine Näherung, nie die exakte Antwort
Antwort zeigen
Richtige Antwort: O(n × W) hängt vom Wert W ab, der in seiner Bitlänge exponentiell ist
Erklärung
Die Tabelle hat W Spalten, und jedes zusätzliche Bit in W verdoppelt sie, die Arbeit ist also exponentiell in der Eingabegröße. Das Rucksackproblem ist NP-schwer; die DP ist nur schnell, wenn Kapazitäten kleine ganze Zahlen sind.