University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677
A Pseudo-Polynomial Time Dynamic Programming Algorithm for the
Knapsack Problem
Revised November 4, 2005
![](../../bluhorsa.gif)
-
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
x1, x2,
, xn
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(2n) 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
x1, x2,
, xm
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:
-
If
0 < m ≤ n
and
0 ≤ t ≤ K,
there is an edge from
S(m - 1, t)
to
S(m, t) .
-
If
0 < m ≤ n
and
xm ≤ t ≤ K,
there is an edge from
S(m - 1, t - xm)
to
S(m, t) .
-
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:
-
For any m ≤ 0,
S(m, 0) = true.
-
For any t > 0,
S(0, t) = false.
-
For any t > 0
and any m > 0:
if t < xm then
S(m, t) = S(m - 1, t)
else
S(m, t) = S(m - 1, t) or S(m - 1, t - xm)
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 xi
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.
![](../../bluhorsa.gif)