Come trovare gli elementi nella borsa, usando l'algoritmo a zaino [e non solo il valore della borsa]?

Question

Ci Ho un codice, che calcola il valore ottimale tramite algoritmo zaino (bin packing problema NP-hard):

int Knapsack::knapsack(std::vector<Item>& items, int W) 
{ 
    size_t n = items.size(); 
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n + 1, 0)); 
    for (size_t j = 1; j <= n; j++) 
    { 
     for (int w = 1; w <= W; w++) 
     { 
      if (items[j-1].getWeight() <= w) 
      { 
       dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight()); 
      } 
      else 
      { 
       dp[w][j] = dp[w][j - 1]; 
      } 
     } 
    } 
    return dp[W][n]; 
} 

Inoltre ho bisogno degli elementi, incluso per imballare, per essere mostrato. Voglio creare un array, per inserire elementi aggiunti. Quindi la domanda è in quale fase aggiungere questa aggiunta, o forse c'è un altro modo più efficace per farlo?

Domanda: Voglio essere in grado di conoscere gli elementi che mi danno la soluzione ottimale e non solo il valore della soluzione migliore.

PS. Scusa per il mio inglese, non è la mia lingua madre.

Answer 1

ottenere gli elementi che impacchettate dalla matrice può essere eseguito utilizzando il modulo dati della matrice, senza memorizzare alcun dato aggiuntivo. Codice
pseudo:

line <- W 
i <- n 
while (i> 0): 
    if dp[line][i] - dp[line - weight(i)][i-1] == value(i): 
     the element 'i' is in the knapsack 
     i <- i-1 //only in 0-1 knapsack 
     line <- line - weight(i) 
    else: 
     i <- i-1 

L'idea alla base: eseguire iterazioni la matrice, se la differenza di peso è esattamente le dimensioni dell'elemento, è nello zaino.
Se non lo è: l'oggetto non è nello zaino, vai avanti senza di esso.

Answer 2

line <- W 
i <- n 
while (i> 0): 
    if dp[line][i] - dp[line - weight(i) ][i-1] == value(i): 
    the element 'i' is in the knapsack 
    cw = cw - weight(i) 
    i <- i-1 
    else if dp[line][i] > dp[line][i-1]: 
    line <- line - 1 
    else: 
    i <- i-1 

Basta ricordare come si è arrivati ​​a dp [line] [i] quando è stato aggiunto voce i

dp[line][i] = dp[line - weight(i) ][i - 1] + value(i); 

Answer 3

Ecco un'implementazione julia:

function knapsack!{F<:Real}(
    selected::BitVector, # whether the item is selected 
    v::AbstractVector{F}, # vector of item values (bigger is better) 
    w::AbstractVector{Int}, # vector of item weights (bigger is worse) 
    W::Int,     # knapsack capacity (W ≤ ∑w) 
    ) 

    # Solves the 0-1 Knapsack Problem 
    # https://en.wikipedia.org/wiki/Knapsack_problem 
    # Returns the assigment vector such that 
    # the max weight ≤ W is obtained 

    fill!(selected, false) 

    if W ≤ 0 
     return selected 
    end 

    n = length(w) 
    @assert(n == length(v)) 
    @assert(all(w .> 0)) 

    ########################################### 
    # allocate DP memory 

    m = Array(F, n+1, W+1) 
    for j in 0:W 
     m[1, j+1] = 0.0 
    end 

    ########################################### 
    # solve knapsack with DP 

    for i in 1:n 
     for j in 0:W 
      if w[i] ≤ j 
       m[i+1, j+1] = max(m[i, j+1], m[i, j-w[i]+1] + v[i]) 
      else 
       m[i+1, j+1] = m[i, j+1] 
      end 
     end 
    end 

    ########################################### 
    # recover the value 

    line = W 
    for i in n : -1 : 1 
     if line - w[i] + 1 > 0 && m[i+1,line+1] - m[i, line - w[i] + 1] == v[i] 
      selected[i] = true 
      line -= w[i] 
     end 
    end 

    selected 
end