Modo ottimale di riempire 2 zaini?

Question

L'algoritmo di programmazione dinamica per riempire in modo ottimale uno zaino funziona bene nel caso di uno zaino. Ma esiste un algoritmo efficiente ed efficace che riempirà in modo ottimale 2 zaini (le capacità possono essere disuguali)?

Ho provato i seguenti due approcci e nessuno di essi è corretto.

1. Prima riempire il primo zaino utilizzando l'algoritmo DP originale per riempire uno zaino e quindi riempire l'altro zaino.
2. Prima riempire uno zaino della misura W1 + W2 e quindi dividere la soluzione in due soluzioni (dove W1 e W2 sono le capacità dei due zaini).

dichiarazione del problema (vedi anche Knapsack Problem su Wikipedia):

1. Dobbiamo riempire lo zaino con una serie di articoli (ogni elemento ha un peso e un valore) in modo da massimizzare il valore che possiamo ottenere dagli articoli pur avendo un peso totale inferiore o uguale alla dimensione dello zaino.

2. Non è possibile utilizzare un elemento più volte.

3. Non è possibile utilizzare una parte di un articolo. Non possiamo prendere una frazione di un oggetto. (Ogni oggetto deve essere completamente incluso o meno).

Answer 1

Suppongo che ciascuno degli articoli n possa essere utilizzato una sola volta e che sia necessario massimizzare i profitti.

zaino originale è dp[i] = best profit you can obtain for weight i

for i = 1 to n do 
    for w = maxW down to a[i].weight do 
    if dp[w] < dp[w - a[i].weight] + a[i].gain 
     dp[w] = dp[w - a[i].weight] + a[i].gain 

Ora, dal momento che abbiamo due zaini, possiamo usare dp[i, j] = best profit you can obtain for weight i in knapsack 1 and j in knapsack 2

for i = 1 to n do 
    for w1 = maxW1 down to a[i].weight do 
    for w2 = maxW2 down to a[i].weight do 
     dp[w1, w2] = max 
        { 
         dp[w1, w2], <- we already have the best choice for this pair 
         dp[w1 - a[i].weight, w2] + a[i].gain <- put in knapsack 1 
         dp[w1, w2 - a[i].weight] + a[i].gain <- put in knapsack 2 
        } 

Tempo complessità è O(n * maxW1 * maxW2), dove maxW è il peso massimo lo zaino può trasportare. Si noti che questo non è molto efficiente se le capacità sono grandi.

Answer 2

Il DP originale presuppone di contrassegnare nell'array dp i valori che è possibile ottenere nello zaino e gli aggiornamenti vengono eseguiti considerando gli elementi.
In caso di 2 zaini è possibile utilizzare array dinamico 2-dimensionale, così dp [i] [j] = 1 quando si può mettere il peso i alla prima e peso j a seconda zaino. L'aggiornamento è simile al caso DP originale.

Answer 3

La formula ricorsiva è nessuno è alla ricerca:

n elementi dato, in modo tale che i ha voce wi peso e il valore pi greco. I due zaini hanno capacità di W1 e W2.

Per ogni 0 < = i < = n, 0 < = a < = W1, 0 < = b = < W2, denotano M [i, a, b] il valore massimo.

per un < 0 oppure b < 0 - M [i, a, b] = -∞ per i = 0, o, b = 0 - M [i, a, b] = 0

La formula: M [i, a, b] = max {M [i-1, a, b], M [i-1, a-wi, b] + pi, M [i-1, a, b-wi] + pi}

Ogni soluzione al problema con gli articoli ha o l'articolo 1 nello zaino 1, nello zaino 2, o in nessuno di essi.