如何使用背包algorithm来find包中的元素？

在那里我有一个代码，它通过背包algorithm（bin packing NP-hard 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]; } 

另外，我还需要显示包含在内的元素。 我想创build一个数组，把那里添加一个元素。 所以问题是在哪一步join，或者还有其他更有效的方法来做到这一点？

问题：我希望能够了解给出最佳解决scheme的项目，而不仅仅是最佳解决scheme的价值。

PS。 对不起，我的英文，这不是我的母语。

Answer 1

从matrix中获取元素可以使用matrix的数据来完成，而不需要存储任何额外的数据。
伪代码：

 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 

它背后的想法是 ：迭代matrix，如果权重差正好是元素的大小，那就是背包。
如果不是：这个东西不在背包里，那就不要这样。

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][i] = dp[line - weight(i) ][i - 1] + value(i); 

Answer 3

这是一个茱莉亚实施：

 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