0-1 sacs à dos sans répétition

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.

Answer 1

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 $

.

.