The knapsack problem comes up quite often and it is important to know how to solve it. For example, given a certain material budget and the cost vs. perceived value of building various edges in a potential road network, which edges should one build? The goal is to optimise the perceived value of the built roads within the fixed material budget.

I recently encountered this problem within a TopCoder marathon match. This post discusses two solutions and the code that I’ll likely reuse for this problem in future.

In terms of a knapsack, given a collection of objects (each with a weight and value ) as well as a knapsack that can carry a certain weight , which objects would you choose to pack? The goal is to optimise the total value of the objects that one can fit into the weight budget of the knapsack.

The below solutions are for the 0-1 knapsack problem which restricts the number of ‘copies’ of each of the n objects to zero or one.

More formally, the goal is to maximize subject to and .

A Greedy Approximate Solution

The ‘greedy’ approach to solving the problem is to repeatedly choose the best value per weight object until no more objects can be added to the knapsack. This solution has a complexity of for m the number of items that typically fit into the knapsack.

For example, given three objects with weights and values and . The value per weight scores for these objects are , , .

For a greedy approach one would try to first choose object two, then object one and then object three. However, one can only fit object two () in the knapsack. Adding either object one or three () would make the knapsack heavier than . Therefore, the greedy solution is a knapsack value .

A greedy solution is however often not optimal. A better solution would have been to rather pack objects one and three with weight and value .

A Dynamic Programming Solution

A solution that uses dynamic programming exists that can find the optimal solution. Dynamic programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems. Another well known example of such a solution is Dijkstra’s algorithm for the shortest path problem.

For the 0-1 knapsack problem define to be the maximum value that can be attained with weight less than or equal to using the set of objects.

We can define recursively as follows:

  • ,
  • if ,
  • if .

The maximum value of the objects that can be packed in the knapsack may then be found by calculating . The C++ code for this would look like:

  for (int w=0; w <= W_; ++w) {
    m[0][w] = 0;
  }
  
  for (int i=1; i <= n; ++i) {
    for (int w=0; w <= W; ++w) {
        if (w[i-1] > w) {
            m[i][w] = m[i-1][w];
        }
        else {
            m[i][w] = std::max(m[i-1][w], m[i-1][w-w[i-1]] + v[i-1]);
        }
    }
  }

For the above three object example, ends up as a table of rows by columns:

  w=0 w=1 w=2 w=3 w=4 w=5
i=0 0 0 0 0 0 0
i=1 0 0 0 8 8 8
i=2 0 0 0 8 12 12
i=3 0 0 5 8 12 13

From the table one can see that is a knapsack of value 13 and building the table has a time complexity of .

The code to find the objects used in the solution is interesting and looks like:

  int i = n;
  int w = W;

  do {
      if (m[i][w] != m[i-1][w])
      {//Object i (1 indexed) seems to have contributed to the value and 
       //must therefore be part of the solution.
          object_used[i-1] = true; // i-1 gives zero indexed object!
          w -= w[i-1]; // Subtract the weight of this object so that 
                       // traversal continues from m[i-1][w - w[i-1]].
      }
      i -= 1;
  } while (i>0);

Note that the dynamic programming solution is a lot slower than the greedy solution and uses LOTS more memory. To solve the problem with knapsack weight of and objects requires a table of size . The table size can quickly become prohibitive. I’ll do a future post on using a search strategy like simulated annealing to find good solutions to very big knapsack problems.

The full source with execution timing is available in my Bits-O-Cpp repo. I use this repo as a reference for myself, but I aim to also maintain examples of how anyone can use those bits of sweet C++ code.