Est-ce que le problème du butin NP-dur quand $ v_i= i $?

Question

Le problème du sac à dos est le NP-dur et peut être formulé comme suit: $$ \ commencez {Align} & \ Text {optimise} \ sum_ {i= 1} ^ n v_i x_i, \ tag {p1} \\ & \ texte {soumis à} \ somm_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ texte {and} x_i \ in \ {0,1 \ \ \ \ fin {align} $$

Et si $ v_i= i $ ?Est-ce toujours np-dur?

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

J'essaie de réduire (P1) à (P2).Compte tenu d'une instance de (P1), je crée le même nombre d'articles, mêmes poids.Maintenant, je dois relier les solutions à (P1) et (p2).

Answer 1

Non, ce problème est dans $ \ mathbf {p} $ . Le point principal étant que la somme de toutes les valeurs est 1 + 2 \ ldots + n=frac {n (n + 1)} {2}=mathcal {o \ mathcal {o} ( n ^ 2) $ , qui est polynomial dans la taille d'entrée. Sans la restriction supplémentaire de $ v_i= i $ , la somme de toutes les valeurs pourrait être exponentielle dans la taille d'entrée, car les valeurs sont représentées en binaire dans l'entrée.

afin que nous puissions définir $ dp [i] [v] $ , où $ 1 \ LEQ i \ Leq n $ et $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , pour être le poids minimum nécessaire pour obtenir une valeur d'au moins $ v $ , en utilisant uniquement la première $ i $ articles. S'il ne peut pas être atteint, nous allons définir $ dp [i] [v]= inf $ . La réponse finale est le maximum $ V $ tel que $ dp [n] [v] \ Leq w $ .

Les valeurs DP peuvent être calculées comme suit:

$ dp [i] [v]=min (dp [i-1] [v], w_i + dp [I-1] [v - v_i]) $ .

Le premier terme considère la possibilité de la $ i ^ {th} $ non choisi et que le second terme est la possibilité qu'il soit choisi. < / p>

afin que tout le problème puisse être résolu dans $ \ mathcal {o} (n ^ 3) $ temps et $ \ mathcal {o} (n ^ 3) $ espace, qui peut être réduit à $ \ mathcal {o} (n ^ 2) $ espace Il suffit de réutiliser deux matrices de taille $ \ frac {n (n + 1)} {2} + 1 $ .

.