Il problema del mal di zaino è difficile quando $ v_i= I $?

Question

Il problema dello zaino è NP-HARD e può essere formulato come: $$ \ Begin {alline} & \ text {maximize} \ sum_ {i= 1} ^ n v_i x_i, \ tag {p1} \\ & \ Text {soggetto a} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {e} x_i \ in \ \ {0,1 \}. \ end {allinea} $$

Cosa succede se $ v_i= i $ ?È ancora NP-HARD?

$$ \ begin {alline} & \ text {maximize} \ sum_ {i= 1} ^ n ix_i, \ tag {p2} \\ & \ Text {soggetto a} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {e} x_i \ in \ \ {0,1 \}. \ end {allinea} $$

Sto cercando di ridurre (P1) a (P2).Dato un'istanza di (P1), creo lo stesso numero di elementi, stessi pesi.Ora, devo mettere in relazione le soluzioni a (P1) e (P2).

Answer 1

No, questo problema è in $ \ mathbf {p} $ . Il punto principale è che la somma di tutti i valori è $ 1 + 2 \ ldots + n=frac {n (n + 1)} {2}=mathcal {o} ( n ^ 2) $ , che è polinomiale nella dimensione di ingresso. Senza la restrizione extra di $ V_I= I $ , la somma di tutti i valori potrebbe essere esponenziale nella dimensione di ingresso, poiché i valori sono rappresentati in binario nell'input.

Così possiamo definire $ DP [i] [v] $ , dove $ 1 \ Leq I \ Leq N $ e $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , per essere il peso minimo necessario per ottenere un valore di almeno $ V $ , utilizzando solo la prima classe $ i $ articoli. Se non può essere raggiunto, impostiamo $ DP [I] [V]= inf $ . La risposta finale è la massima $ V $ in modo tale che $ dp [n] [v] \ leq w $ .

I valori DP possono essere calcolati come segue:

$ DP [I] [V]=min (DP [I-1] [V], W_i + DP [I-1] [V - V_I]) $ .

Il primo mandato considera la possibilità della $ i ^ {th} $ Articolo non viene scelto e il secondo termine è la possibilità che sia scelto. < / P >.

Quindi l'intero problema può essere risolto in $ \ mathcal {o} (n ^ 3) $ tempo e $ \ Mathcal {o} (n ^ 3) $ spazio, che può essere ridotto a $ \ mathcal {o} (n ^ 2) $ Spazio di Basta riutilizzare due array di dimensioni $ \ frac {n (n + 1)} {2} + 1 $ .