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);