Jak znaleźć elementy w torbie, używając algorytmu plecakowego [a nie tylko jego wartości]?

Question

Nie mam kod, który oblicza optymalną wartość przez algorytm plecakowy (bin pakowania NP-trudny problem):

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]; 
} 

Również muszę elementy, włączone do pakowania, które mają być pokazane. Chcę utworzyć tablicę, aby umieścić tam dodatkowe elementy. Pytanie brzmi, na jakim etapie umieścić ten dodatek, a może jest jakiś inny bardziej skuteczny sposób na zrobienie tego?

Pytanie: Chcę być w stanie poznać przedmioty, które dają mi optymalne rozwiązanie, a nie tylko wartość najlepszego rozwiązania.

PS. Przepraszam za mój angielski, to nie jest mój język ojczysty.

Answer 1

pobieranie elementów z matrycy odbywa się za pomocą danych z matrycy, bez przechowywania żadnych dodatkowych danych. kod
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 

Ideą: iteracyjne matrycy, jeśli różnica wagi jest dokładnie rozmiar elementu, to jest w plecaku.
Jeśli nie jest: przedmiot nie jest w plecaku, bez niego dalej.

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 

Wystarczy pamiętać, jak masz DP [wiersz] [i], jeśli dodana pozycja I

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

Answer 3

Oto realizacja 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