Wir wissen, dass das Rucksackproblem durch dynamische Programmierung in O (nW) -Komplexität gelöst werden kann. Wir sagen jedoch, dass dies ein NP-vollständiges Problem ist. Ich finde es hier schwer zu verstehen.

(n ist die Anzahl der Elemente. W ist die maximale Lautstärke.)