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.

Solution 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.

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

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

Comments

[prvit]

It's really nice pseudo code. But using it i can get only the weight of added element, and i need their name also. I'm thinking about doint the same, but to change array dp to an Item type. What's your point about it?

[amit]

@nightcrime: Using this alorithm, you know EXACTLY which element is in the bag, you can create a container before you start this algorithm [let's call it bag, and while running the algorithm: if dp[line][i] - dp[line][i-1] == value(i) then bag.add(items[i-1]), where items is the input vector of items to your knapsack function. At the end of the algorithm, bag will contain all the elements in the bag, and only them.

[prvit]

:I've got it. But it works only and only if i've added only 1 element. In other ways the statement dp[line][i] - dp[line][i-1] == value(i) never is true.(

[amit]

@nightcrime: I am not sure I am following you, the knapsack algorithm, and so does my answer, doesn't allow you to add the item 'i' to the bag twice [or 3/4/.. times]. if you add elements i,j,k: this algorithm will find all of them, since dp[line][i]-dp[line][i-1] == value(i), dp[line][j]-dp[line][j-1] == value(j) and dp[line][k]-dp[line][k-1] == value(k).

[prvit]

I want to clarify one thing: value(i) in my example is items[i-1].getWeight() isn't it?

[prvit]

Oh, I used items[i] instead of items[i-1]. Very stupid mistake:) Thanks, you really rescued me:)

[Rushil Paul]

you could also simply check if dp[line][i] != dp[line][i-1]. if that is true, then the ith item is taken.

[Sazid]

Be careful when doing line - weight(i) as weight of some items may be larger than the knapsack i.e it may give a negative index.