Java Reference
In-Depth Information
Dynamic programming is a powerful alternative to the standard principle of
divide and conquer. In divide and conquer, a problem is split into subproblems,
the subproblems are solved (independently), and then recombined into a solution
for the problem being solved. Dynamic programming is appropriate whenever (1)
subproblems are solved repeatedly, and (2) we can find a suitable way of doing the
necessary bookkeeping. Dynamic programming algorithms are usually not imple-
mented by simply using a table to store subproblems for recursive calls (i.e., going
backwards as is done by
Fibrt
). Instead, such algorithms are typically imple-
mented by building the table of subproblems from the bottom up. Thus,
Fibi
bet-
ter represents the most common form of dynamic programming than does
Fibrt
,
even though it doesn't use the complete table.
16.1.1 The Knapsack Problem
We will next consider a problem that appears with many variations in a variety
of commercial settings. Many businesses need to package items with the greatest
efficiency. One way to describe this basic idea is in terms of packing items into
a knapsack, and so we will refer to this as the Knapsack Problem. We will first
define a particular formulation of the knapsack problem, and then we will discuss
an algorithm to solve it based on dynamic programming. We will see other versions
of the knapsack problem in the exercises and in Chapter 17.
Assume that we have a knapsack with a certain amount of space that we will
define using integer value K. We also have n items each with a certain size such
that that item i has integer size k
i
. The problem is to find a subset of the n items
whose sizes exactly sum to K, if one exists. For example, if our knapsack has
capacity K = 5 and the two items are of size k
1
= 2 and k
2
= 4, then no such
subset exists. But if we add a third item of size k
3
= 1, then we can fill the knapsack
exactly with the first and third items. We can define the problem more formally as:
Find S f1; 2;:::;ng such that
X
k
i
= K:
i2S
Example16.1
Assume that we are given a knapsack of size K = 163
and 10 items of sizes 4, 9, 15, 19, 27, 44, 54, 68, 73, 101. Can we find a
subset of the items that exactly fills the knapsack? You should take a few
minutes and try to do this before reading on and looking at the answer.
One solution to the problem is: 19, 27, 44, 73.
Example16.2
Having solved the previous example for knapsack of size
163, how hard is it now to solve for a knapsack of size 164?
