0-1 sacs à dos sans répétition
-
29-09-2020 - |
Question
Ma question est la raison pour laquelle O (NW) au problème du knapsack est pseudo-polynomial.
J'ai lu beaucoup d'explication à Stackoverflow, mais je ne comprends pas vraiment. ( https://stackoverflow.com/questions/4538581/Why- is-the-knapsack-problem-pseudo-polynomial # réponse-4538668 )
La chose essentielle est la raison pour laquelle nous devons ne penser que "W" comme "logw" entrée, pas "n" comme "journal n 'bits"
Les nombreuses explications ont déclaré que "W" est entier mais "N" n'est que le nombre d'articles. Par conséquent, seule la taille 'w' est proportionnelle à "logw".
Je pense que cette logique doit être appliquée à 'N'.
En supposant que nous numéroons les éléments de 1 à n, pour différencier les éléments,
Nous devons compter les chiffres de 1 à n.
Je pense que c'est la même chose que la boucle utilise l'itération pour W Times.
Par conséquent, je pense que c'est la même chose avec 'W' parce que ce comptage nécessite également des bits "log n".
Qu'est-ce que je suis mal compris à ce problème?
merci.
La solution
Voici comment vous encodez l'entrée:
- Poids et valeur de l'article 1.
- Poids et valeur du point 2.
- ...
- Poids et valeur de l'élément $ N $ .
- $ w $ .
Supposons que le poids et la valeur sont des entiers, sont au plus $ m $ , et les deux sont codés en binaire, de même que $ W $ .Puis la longueur du codage est $$ \ Oméga (n + \ log w), O (n \ journal m + \ log w). $$ J'espère que cela clarifie la différence entre $ n $ et $ w $
. .