How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Question

Here I have code which calculates the optimal value using the 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];
}

I also need the elements included in the pack to be shown. I want to create an array to put the chosen elements. So the question is, in which step can I perform this selection? Is there any other more efficient way to determine which items have been taken?

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

Answer 1

Getting the elements you packed from the matrix can be done using the data from 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 is that 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.

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

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

Answer 3

The algorithm for reconstructing items taken in bounded 0/1 knapsack is simpler than some of the existing code in this thread may lead one to believe. This answer aims to demystify the procedure a bit and provide a clean, direct implementation alongside a worked example.

---

The approach

Begin with two indices respective to the table axes: a weight variable initialized to the knapsack capacity and an index i that loops backwards over the DP lookup table along the item axis, stopping at index 1 (the algorithm uses i-1 so stopping at 1 avoids an out of bounds access).

In the loop, if T[weight][i] != T[weight][i-1], mark item i-1 as selected, deduct its weight and continue stepping backwards along the item axis.

Time complexity of the reconstruction is O(length(items)).

Here is Python as pseudocode:

def reconstruct_taken_items(T, items, capacity):
    taken = []
    weight = capacity

    for i in range(len(items), 0, -1): # from n downto 1 (inclusive)
        if T[weight][i] != T[weight][i-1]:
            taken.append(items[i-1])
            weight -= items[i-1].weight

   return taken

---

Example

For example, consider a knapsack capacity of 9 and these items:

[item(weight=1, value=2), 
 item(weight=3, value=5), 
 item(weight=4, value=8), 
 item(weight=6, value=4)]

The best value is 15 by taking items 0, 1 and 2.

The DP lookup table is

items ---->

0  1  2  3  4
--------------+
0  0  0  0  0 | 0  capacity
0  2  2  2  2 | 1     |
0  2  2  2  2 | 2     |
0  2  5  5  5 | 3     v
0  2  7  8  8 | 4
0  2  7 10 10 | 5
0  2  7 10 10 | 6
0  2  7 13 13 | 7
0  2  7 15 15 | 8
0  2  7 15 15 | 9

Run the reconstruction algorithm on this:

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15 <-- weight = capacity = 9
        ^   ^
        |   |
      i-1   i = length(items) = 4

In the initial state above, T[weight][i] == T[weight][i-1] (15 == 15) so item[i-1] (item(weight=6, value=4)) wasn't taken. Decrement i and try the remaining items with the same capacity.

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15 <-- weight = 9
        ^
        |
        i = 3

Here, T[weight][i] != T[weight][i-1] (7 != 15) so items[i-1], which is items[2], or item(weight=4, value=8), must have been taken. Decrement the weight remaining by items[i-1].weight, or 9 - 4 = 5, and try the remaining items with the smaller weight left over after taking item[i-1] out of the picture.

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10 <-- weight = 5
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15
      ^
      |
      i = 2

In this state, we again have T[weight][i] != T[weight][i-1] (2 != 7) so we must have taken items[i-1], which is items[1], or item(weight=3, value=5). Decrement the weight remaining by items[i-1].weight, or 5 - 3, and move to the next item.

0  0  0  0  0
0  2  2  2  2
0  2  2  2  2 <-- weight = 2
0  2  5  5  5
0  2  7  8  8
0  2  7 10 10
0  2  7 10 10
0  2  7 13 13
0  2  7 15 15
0  2  7 15 15
   ^
   |
   i = 1

In this last step, we again have T[weight][i] != T[weight][i-1] (0 != 2) so we must have taken items[i-1], which is items[0], or item(weight=1, value=2). Decrement the weight remaining by items[i-1].weight, or 2 - 1, and exit the loop because i == 0.

---

C++ implementation

#include <iostream>
#include <vector>

class Knapsack {
public:
    struct Item {
        const int weight;
        const int value;
    };

private:
    static std::vector<Item> reconstruct_taken_items(
        const std::vector<std::vector<int> > &T,
        const std::vector<Item> &items,
        const int capacity
    ) {
        std::vector<Item> taken;
        int weight = capacity;
    
        for (size_t i = items.size(); i > 0; i--) {
            if (T[weight][i] != T[weight][i-1]) {
                taken.emplace_back(items[i-1]);
                weight -= items[i-1].weight;
            }
        }
    
        return taken;
    }

public:
    static std::vector<Item> solve(
        const std::vector<Item> &items, 
        const int capacity
    ) {
        std::vector<std::vector<int> > T(
            capacity + 1,
            std::vector<int>(items.size() + 1, 0)
        );
        
        for (int i = 1; i <= capacity; i++) {
            for (size_t j = 1; j <= items.size(); j++) {
                const Item &item = items[j-1];

                if (item.weight > i) {
                    T[i][j] = T[i][j-1];
                }
                else {
                    T[i][j] = std::max(
                        T[i-item.weight][j-1] + item.value, 
                        T[i][j-1]
                    );
                }
            }
        }
        
        return reconstruct_taken_items(T, items, capacity);
    }
};

int main() {
    const int capacity = 9;
    const std::vector<Knapsack::Item> items = {
        {1, 2}, {3, 5}, {4, 8}, {6, 4}
    };

    for (const Knapsack::Item &item : Knapsack::solve(items, capacity)) {
        std::cout << "weight: " << item.weight 
                  << ", value: " << item.value << "\n";
    }

    return 0;
}

---

See also

• Printing Items that are in sack in knapsack
• Knapsack 0-1 path reconstruction (which items to take)

Answer 4

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