How to find which elements are in the bag, using K

问题:

There I have a code, which calculates the optimal value by knapsack 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];
}

Also I need the elements, included to pack, to be shown. I want to create an array, to put there an added elements. So the question is in which step to put this addition, or maybe is there any other more efficient way to do it?

Question: I want to be able to know the items that give me the optimal solution, and not just the value of the best solution.

PS. Sorry for my English, it's not my native language.

回答1:

getting the elements you pack from the matrix can be done using the data form the matrix, without storing any additional data.
pseudo code:

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 

The idea behind it: you iterate the matrix, if the weight difference is exactly the element's size, it is in the knapsack.
If it is not: the item is not in the knapsack, go on without it.

回答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

Just remember how you got to dp[line][i] when you added item i

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

回答3:

Here is a julia implementation:

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