Как найти, какие элементы находятся в сумке, используя алгоритм Knapsack Algorithm [а не только значение мешка]?

Там у меня есть код, который вычисляет оптимальное значение по алгоритму ранца (бит-упаковка 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. Извините за мой английский, это не мой родной язык.

Ответы

Ответ 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

Идея этого: вы перебираете матрицу, если разница в весе равна размеру элемента, она находится в рюкзаке.
Если это не так: предмет не находится в рюкзаке, продолжайте без него.

Ответ 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

Просто помните, как вы добрались до dp [line] [i], когда вы добавили элемент i

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

Ответ 3

Вот реализация 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