Come trovare gli elementi nella borsa, usando Algoritmo a zaino ?

Lì ho un codice, che calcola il valore ottimale dall’algoritmo dello zaino (bin packing NP-hard problem):

int Knapsack::knapsack(std::vector& items, int W) { size_t n = items.size(); std::vector<std::vector > dp(W + 1, std::vector(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, inclusi nel pacchetto, da mostrare. 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.

    ottenere gli elementi che impacchettate dalla matrice può essere fatto usando i 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 : si itera la matrice, se la differenza di peso è esattamente la dimensione dell'elemento, è nello zaino.
    Se non lo è: l'object non è nello zaino, vai avanti senza di esso.

     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 

    Ricorda solo come hai ottenuto dp [line] [i] quando hai aggiunto l'elemento i

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

    Ecco un’implementazione di 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, jw[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