How to solve the integral Knapsack Problem
Problem statement
Suppose you have a knapsack with capacity M and a set I of N items i characterised by their weight W(i) and their value V(i). Weights are represented by non-negative integers. Values are represented by arbitrary non-negative numbers.
We want to select a set X of items, so that the sum V(X) of the values of all members of X is maximised and the sum of the weights does not exceed the capacity of the knapsack.
The image below shows an example where all items are characterised by their weight in purple and their value in orange.
By brute force, we can figure out that the best possible solution when the overall weight mustn’t exceed 6 is 12. It is obtained with the following subset of items:
Why dynamic programming?
As we saw in the first two parts, dynamic programming can solve problems which have an optimal substructure and is useful when subproblems are overlapping (otherwise, a simple divide-and-conquer approach suffices).
Optimal substructure
Let’s see how we can build a solution to the problem from solutions to smaller subproblems. This will enable us to establish a recurrence relation which we’ll use to write our algorithm.
Suppose the set I of all items is ordered (and indexable). Let Opt(n, m) denote the sum of the values of an optimal solution to a reduced instance of the original problem, with maximum capacity m and a set of items consisting of the first n elements of I. This instance of the Knapsack problem will be denoted Knap(n, m).
First of all, for all n and m we have Opt(n, 0) = Opt(0, m) = 0: in both cases, we cannot store any item so their values add up to 0.
If n and m are positive, let S be an optimal set which solves Knap(n, m), that is, a subset of the first n items such that V(S) = Opt(n, m).
Let’s consider the n-th item. We’ll call it x. If x is not in S then S is still a solution to Knap(n-1, m). In fact, it is optimal. Therefore, Opt(n-1, m) = Opt(n, m).
Proof:
Suppose S does not solve optimally Knap(n-1, m). This means that V(S) < Opt(n-1, m). Plugging V(S) = Opt(n, m), we get Opt(n, m) < Opt(n-1, m). But if some set U solves Knap(n-1, m) (optimally or not), then it also solves Knap(n, m) (we are not obliged to use the n-th item), and therefore Opt(n-1, m) ≤ Opt(n, m).
This gives a contradiction: S must be an optimal solution to Knap(n-1, m).
If on the contrary, x does belong to S then S∖{x} is a solution to Knap(n-1, m-W(x)). We’ll prove that this solution is optimal. It shows that Opt(n-1, m-W(x)) + V(x) = Opt(n, m).
Proof:
Let S’ := S∖{x}. Then V(S’) = Opt(n, m) - V(x). Suppose S’ is not optimal, i.e. V(S’) < Opt(n-1, m-W(x)). Then V(S’) + V(x) < Opt(n-1, m-W(x)) + V(x), i.e. Opt(n, m) < Opt(n-1, m-W(x)) + V(x).
If we take a set which optimally solves Knap(n-1, m-W(x)) and add x to it, then we would have a set Y which solves Knap(n, m) and satisfies V(Y) = Opt(n-1, m-W(x)) + V(x). Therefore, V(Y) ≤ Opt(n, m), i.e. Opt(n-1, m-W(x)) + V(x) ≤ Opt(n, m).
The two conclusions in bold contradict each other. Therefore, S’ must be optimal.
We can bring all these pieces together and establish our final recurrence relation:
- If W(x) > m then x is certainly not in a set which solves Knap(n, m). Therefore, Opt(n, m) = Opt(n-1, m).
- Otherwise, the optimal solution may be the same as Knap(n-1, m), or may be constructed by adding x to a set which optimally solves Knap(n, m-W(x)). Therefore, Opt(n, m) = max {Opt(n-1, m}, Opt(n-1, m-W(x)) + V(x)}.
Overlapping subproblems
Many computations would end up being performed multiple times if we naïvely implemented the recurrence relation. If the function performs two recursive calls every time it is called — one to calculate Opt(n-1, m) and one to calculate Opt(n-1, m-W(x)) — then the complexity would be exponential, exceeding the total of NM necessary computations.
Writing a solution
Writing a solution is quite straightforward now that we have a recurrence relation. It takes three parameters: two arrays, weights and values, and the maximum capacity. The weight and value of the i-th item are given by weights[i] and value[i].
The cache opt is a two-dimensional array of size N×M, where N is the number of items and M is the maximum capacity. We’ll populate it in a bottom-up manner.
The routine in lines 8 to 19 is a direct implementation of the recurrence. Lines 21 to 23 manage recursive calls. The first condition checks if we’ve computed the final result, in which case we return the optimal solution. Otherwise, we either compute Opt(n+1, m) if it makes sense (if n + 1 ≤ N), or move on to the following value of m, starting at n = 0.
The non-recursive overhead of our solution takes constant time. Therefore, this solution takes Θ(NM) time and space.
Sparse matrix and top-down approach
We can notice that some computations are unnecessary. If items have weights 4, 8 and 15 — in this order—and the maximum capacity is 15, then the parameter m could could be limited to values 15, 7, 11 and 3 rather than all integers between 1 and 15. Theses values correspond to capacity residuals: M is a residual and for all residuals r, for all weights w: r – w is a residual.
This means that the cache matrix is sparse: most values are irrelevant. When encountering a sparse matrix, we often want to consider a top-down approach rather than bottom-up. This helps to avoid performing a large amount of unnecessary computations.
With that in mind, we can rewrite our algorithm using memoisation.
The structure of the algorithm is essentially the same. The three highlighted lines correspond to elements specific to memoisation: we check if the value was previously computed (line 7), we return the value rather than making a tail-recursive call (line 22) and the original call to the recursive function passes the final parameters, not initial values (line 24).
Constructing a solution
In most applications, we are interested in finding an example of optimal set of items rather than just knowing what their value is. As with other dynamic programming problems, we can maintain a second matrix which remembers the decisions we make at every step, without worsening the asymptotic space and time complexity of the original algorithm.
We implement is as follows:
When we construct a solution to Knap(n, m) from a solution to Knap(n-1, m’), with m’ = m or m - W(x), we store n-1 and m in A before returning. Since we select an item exactly when we build then solution from a solution to a subproblem with a smaller capacity, we know what items are in an optimal solution, using the following function:
Your turn!
If you want to implement the solution in a real programming language, I have created a text file for you to test your code:
It has the following format:
n: positive integer
weights: n space-separated positive integers
values: n space-separated positive integers
maximum capacity: positive integer
solution: positive integer
<blank lineImproving the space complexity
If we are only interested in knowing the optimal value the knapsack can carry, we can improve our solution so that it takes O(M) space, instead of O(MN).
We notice that the only recursive calls we perform to solve Knap(n, m) look back to instances of the problem where we consider the first n-1 items. Therefore, it is not useful to store the solutions to all subproblems in an N*M matrix: a 2*M matrix would suffice.
