Changement de complexité de programmation dynamique de la programmation dynamique pour $ W= 1 $, est-ce qu'il est $ (n) $?

Question

Le problème du knapacks 0-1 est donné par

$$ \ commencez {Align} & \ Text {optimiser} \ sum_ {i= 1} ^ n v_ix_i, \ tag {p1} \\ & \ texte {soumis à} \ somm_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ texte {and} x_i \ in \ {0,1 \ \ \ \ fin {align} $$

Exécution de l'algorithme de programmation dynamique de ce problème donnerait une solution optimale dans $ o (nw) $ .

si je définis $ p_i= w_i / w $ , je reçois le problème de Knapack suivant:

$$ \ commencez {Align} & \ Text {optimiser} \ sum_ {i= 1} ^ n v_ix_i, \ tag {p2} \\ & \ Text {Sujet à} \ Sum_ {i= 1} ^ n p_i x_i \ leq 1, \\ & \ texte {and} x_i \ in \ {0,1 \ \ \ \ \ fin {align} $$

Exécution de l'algorithme de programmation dynamique de ce problème donnerait une solution optimale dans $ o (n) $ .Ce n'est pas vrai, n'est-ce pas?

Answer 1

Le temps d'exécution est $ o (nw) $ si tous les poids sont les entiers .En effet, le tableau de programmation dynamique est indexé par des poids possibles des sous-ensembles.Si tous les poids sont des entiers, car nous ne sommes plus intéressés par des sous-ensembles dont la somme de poids est au plus $ w $ , il n'y a que $ W + 1 $ poids des sous-ensembles qui pourraient éventuellement nous intéresser.C'est là que la $ W $ Le facteur de fonctionnement vient de.

Diviser tous les poids par $ W $ n'accorde rien.Vous n'avez pas changé le problème, le temps nécessaire à la résolution de cela reste la même chose.