c++ - multiple - knapsack problem python

¿Cómo encontrar qué elementos están en la bolsa, usando el Algoritmo de mochila[y no solo el valor de la bolsa]?

Question

Ahí tengo un código, que calcula el valor óptimo por el algoritmo de mochila (bin empaquetando el problema de NP-difícil):

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

También necesito que se muestren los elementos, incluidos en el paquete. Quiero crear una matriz, para poner allí un elemento añadido. Entonces, la pregunta es en qué paso colocar esta adición, o tal vez, ¿hay alguna otra forma más eficiente de hacerlo?

Pregunta: Quiero poder conocer los elementos que me dan la solución óptima, y ​​no solo el valor de la mejor solución.

PD. Lo siento por mi inglés, no es mi idioma nativo.

Answer 1

Aquí hay una implementación de 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

Answer 2

puede obtener los elementos que empaqueta de la matriz utilizando los datos de la matriz, sin almacenar ningún dato adicional.
pseudo codigo

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 

La idea que hay detrás : iterar la matriz, si la diferencia de peso es exactamente el tamaño del elemento, está en la mochila.
Si no lo está: el artículo no está en la mochila, continúe sin él.

Answer 3

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

Solo recuerda cómo llegaste a dp [line] [i] cuando agregaste el elemento i

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