Comment comprendre le problème knapsack est NP-complet?

nous savons que le problème knapsack peut être résolu dans la complexité O(nW) par la programmation dynamique. Mais nous disons que c'est un NP-problème complet. Je pense qu'il est difficile à comprendre ici.

(n est le nombre d'éléments. W est le volume maximal.)

65
demandé sur cnhk 2010-10-11 19:17:57

7 réponses

O(n*W) ressemble à un temps polynomial, mais il est pas , il est pseudo-polynomial .

Temps de mesure de complexité le temps que l'algorithme prend en fonction de la longueur en bits de son entrée. La solution de programmation dynamique est en effet linéaire dans la valeur de W , mais exponentielle dans la longueur de W - et c'est ce qui compte!

plus précisément, la complexité temporelle de la solution dynamique pour le problème knapsack est fondamentalement donnée par une boucle imbriquée: 

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

ainsi, la complexité temporelle est clairement O(n*W) .

Que signifie une augmentation linéaire de la taille de l'entrée de l'algorithme? Cela signifie utiliser des tableaux d'articles de plus en plus longs (so n , n+1 , n+2 ,...) et de plus en plus long W (donc, si W est x bits long, après une étape nous utilisons x+1 bits, puis x+2 bits, ...). Mais la valeur de W croît exponentiellement avec x , donc l'algorithme n'est pas vraiment polynomial, il est exponentiel (mais il ressemble à il est polynomial, d'où le nom:" pseudo-polynomial").

Autres Références

39
répondu Giuseppe Cardone 2018-04-04 01:24:59

dans le problème knapsack 0/1, nous avons besoin de 2 entrées(1 Tableau & 1 entier) pour résoudre ce problème:

  1. un tableau de n "151950920 des éléments": [n1, n2, n3, ... ], chaque article avec son indice de valeur et son indice de poids.
  2. entier W comme poids maximal acceptable

supposons n = 10 et W= 8:

  1. n = [n1, n2, n3, ... , n10]
  2. W = 1000 en terme binaire (4 bits de long)

, donc le temps de la complexité T(n) = O(nW) = O(10*8) = O(80)

si vous doublez la taille de n :

n = [n1, n2, n3,... , n10 ] - > n = [n1, n2, n3, ... , n20 ]

donc complexité temporelle T (n) = O (nW) = O (20 * 8) = O(160)

mais comme vous double de la taille de W , cela ne signifie pas W=20, mais la longueur est deux fois long:

W = 1000 - > W = 10000000 en terme binaire (8 bits de long)

so T (n) = O(nW) = O(10*128) = O(1280)

le temps nécessaire augmente en terme exponentiel, donc c'est un NPC problem.

17
répondu YoEugene 2014-12-31 08:32:18

tout dépend des paramètres que vous mettez à l'intérieur de O(...) .

si le poids cible est limité par le nombre W , alors le problème a O(n*W) complexité, comme vous l'avez mentionné.

mais si les poids sont beaucoup trop grands et que vous avez besoin d'un algorithme avec une complexité indépendante de W , alors le problème est NP-complet. ( O(2^n*n) dans la plupart des naïfs mise en œuvre).

6
répondu Nikita Rybak 2010-10-11 15:23:08

c'est parce que le knapsack problem a un pseudo-polynomial solution et est donc appelé faible NP-complète (et non fortement NP-complète" 151970920 ).

4
répondu Manav Kataria 2018-04-04 01:35:42

la taille de l'entrée est log(W) bits pour le poids (et O(n) pour les tableaux" valeur "et" poids").

ainsi, la taille d'entrée du poids est j = log(W) (et pas seulement W ). Ainsi, W = 2ʲ (en binaire est utilisé).

la complexité finale est O(n * W)

Ce O(n * W) peut être réécrit comme O(n * 2ʲ) , qui exponentielle en la taille de l'entrée.

Donc, cette solution n'est pas polynomiale.

3
répondu kaushalpranav 2018-04-05 10:00:52

Vous pouvez lire cette courte explication: La NP-Complétude de sac-à-Dos .

2
répondu dfens 2018-04-03 21:30:29

comprendre NP-complétude , vous avez à apprendre un peu de théorie de la complexité. Cependant, fondamentalement, il est NP-complet parce qu'un algorithme efficace pour le problème knapsack serait également un algorithme efficace pour SAT , TSP et le reste.

0
répondu Pontus Gagge 2018-04-03 21:31:49