Computer Science 477/677
A Pseudo-Polynomial Time Dynamic Programming Algorithm for the Knapsack Problem

Revised November 4, 2005

Definition of the Knapsack Problem. The knapsack problem is a 0/1 problem, meaning that the answer to every instance is either 0 (false, or no) or 1 (true, or yes). An instance of the knapsack problem consists of one number K, called the knapsack size, and a finite sequence x₁, x₂, …, x_n of numbers called the item sizes. The question is: is there a subsequence of the item sizes whose total is the knapsack size?
We assume that the knapsack size and all the item sizes are positive integers.
The brute force method of solving this problem is to simply try every one of the O(2ⁿ) subsequences. Here, we describe a dynamic programming algorithm whose time complexity is O(nK).

The Algorithm For each 0 ≤ m ≤ n and each 0 ≤ t ≤ K define the 0/1 problem instance S(m, t) as follows: S(m, t) is the question of whether there is some subsequence of x₁, x₂, …, x_m whose sum is t. We define a directed graph whose nodes are the S(m, t). This graph has (n+1)(K+1) nodes and no more than 2nK edges. We define the edges as follows:

1. If 0 < m ≤ n and 0 ≤ t ≤ K, there is an edge from S(m - 1, t) to S(m, t) .
2. If 0 < m ≤ n and x_m ≤ t ≤ K, there is an edge from S(m - 1, t - x_m) to S(m, t) .
3. There are no other edges.

The graph is acyclic, and it easy to find a topological order. In fact, row-major order and column-major order are both topological.
We now compute a Boolean value of each S(m, t) in our chosen topological order, as follows:

1. For any m ≤ 0, S(m, 0) = true.
2. For any t > 0, S(0, t) = false.
3. For any t > 0 and any m > 0:
   if t < x_m then S(m, t) = S(m - 1, t)
   else S(m, t) = S(m - 1, t) or S(m - 1, t - x_m)

The answer to the original knapsack problem instance is then the Boolean value of S(n, K).
Note that there is edge from from a node to a node if and only if the value at the first node must be known in order to compute the value at the second node.

Is this Algorithm Polynomial? Yes, it is polynomial in the values of the inputs, but no, it is not polynomial in the size of the input string, which is the number of symbols. These can be very different. For example, if x_i is one billion, then it contributes only 10 symbols to the size of the input string, if it is written in base 10.
You may have heard that the knapsack problem is NP-complete. This is true. There is no known algorithm for the knapsack problem that runs in polynomial time in the length of the input string.