0-1 Zaino senza ripetizione
-
29-09-2020 - |
Domanda
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.
Soluzione
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 $ .