0-1 Rucksack ohne Wiederholung

Question

Meine Frage ist, warum O (NW) am Rucksack-Problem Pseudo-Polynom ist.

Ich las viele der Erklärung bei Stackoverflow, aber ich verstehe es nicht wirklich. ( https://stackoverflow.com/questions / 19647658 / What-is-pseudopolynomial-time-how-it-it-vit-von-polynomial-time , https://stackoverflow.com/questions/4538581/War- IS-the-rucksack-problem-pseudo-Polynom # Antwort-4538668 )

0

Die viele Erläuterungen gaben an, dass 'w' Integer ist, aber 'n' ist nur die Anzahl der Artikel. Daher ist nur 'w' Größe proportional zu "logw".

Ich denke, diese Logik muss auf 'n' angewendet werden.

Angenommen, wir nummerieren die Artikel von 1 bis N, um die Elemente zu differenzieren,

Wir müssen die Zahlen von 1 bis n zählen.

Ich denke, es ist dasselbe, dass die Schleife die Iteration für W-Male macht.

deshalb denke ich, dass es mit 'w' ist, weil diese Zählung auch "log n 'Bits braucht.

Was habe ich bei diesem Problem falsch verstanden?

danke.

Answer 1

So kodieren Sie den Eingang:

.
• Gewicht und Wert von Punkt 1.
• Gewicht und Wert von Punkt 2.
• ...
• Gewicht und Wert des Elements $ n $ .
• $ W $ .

Angenommen, das Gewicht und der Wert handelt es sich an, dass das Gewicht und Wert intengründer ist, höchstens $ M $ , und beide werden in binärer codierter, ebenso wie $ W $ .Dann ist die Länge der Kodierung $$ \ Omega (n + \ log w), o (n \ log m + \ log w). $$ Hoffentlich klärt dies den Unterschied zwischen $ N $ und $ W $ .