バッグの価値だけでなく、ナップザックアルゴリズムを使って、どの要素がバッグに入っているかを見つける方法は？

Question

があり、私はナップザックアルゴリズム（NP困難問題を梱包箱）によって最適値を算出し、コード、持っている：また、私は要素が必要

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

を示すことが、パックに含まれています。私は追加された要素をそこに置くために、配列を作成したい。そこで、この追加をどのステップで行うのか、それとももっと効率的なやり方があるのでしょうか？

質問：私は私に最適な解決策ではなく、最善の解決策の値だけを与える項目を知ることができるようにしたいです。

PS。私の英語は申し訳ありませんが、私の母国語ではありません。

Answer 1

マトリックスからパックする要素を取得するには、追加のデータを保存せずに、マトリックスからデータを使用します。
擬似コード：

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 

それ背後にある考え方：重量差は正確に要素のサイズである場合は、行列を繰り返す、それはナップザックです。
そうでない場合：アイテムがナップザックにない場合は、そのアイテムはなくしてください。

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 

ちょうどあなたが商品を追加するとき、[i]は、私ここ

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

Answer 3

がジュリアの実装であるあなたは、[行]をDPようになった方法を覚えている：

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