0-1 Zaino senza ripetizione

Question

La mia domanda è il motivo per cui O (NW) al problema dello zaino è pseudo-polinomiale.

Leggo un sacco della spiegazione a Stackoverflow, ma non lo capisco davvero. ( https://stackoverflow.com/questions / 19647658 / What-is-pseudopolynomial-how-how-how-it-diversi-from-polinomiale-tempo , https://stackoverflow.com/questions/4538581/Why- is-the-the-waralack-problema-pseudo-polinomiale # risposta-4538668 )

La cosa del nucleo è il motivo per cui dobbiamo pensare solo "w" come ingresso bit "logw", non "n 'come" log n' bit.

Le molte spiegazioni hanno detto che 'w' è intero ma 'n' è solo il numero dell'articolo. Quindi solo la dimensione "w" è proporzionale a "logw".

Penso che questa logica debba essere applicata a 'n'.

Supponendo che stiamo numerando gli articoli da 1 a N, per differenziare gli articoli,

Dobbiamo contare i numeri da 1 a n.

Penso che sia lo stesso che il loop fa iterazione per W volte.

Perciò penso che sia uguale a 'w' perché questo conteggio ha anche bisogno di "log n 'bit.

Cosa capisco male a questo problema?

Grazie.

Answer 1

Ecco come si codifica l'ingresso:

.
• Peso e valore dell'articolo 1.
• Peso e valore dell'articolo 2.
• ...
• Peso e valore dell'articolo $ N $ .
• $ W $ .

Supponiamo che il peso e il valore siano numeri interi, sono al massimo $ M $ , ed entrambi sono codificati in binary, così come $ W $ .Quindi la lunghezza della codifica è $$ \ Omega (n + \ log w), o (n \ log m + \ log w). $$ Speriamo che questo chiarisca la differenza tra $ N $ e $ W $ .