This

**preview**shows pages 1-3. to view the full**26 pages of the document.**1

Dynamic Programming

Dynamic programming was invented by Richard

Bellman in the early 1950’s while he worked for the

RAND corporation on “multistage decision processes”.

• Origins of the term “Dynamic Programming” (1950):

– “What title, what name, could I choose? In the first place I was interested in planning,

in decision making, in thinking. But planning, is not a good word for various reasons. I

decided therefore to use the word, ‘programming.’ I wanted to get across the idea that

this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two

birds with one stone. Let’s take a word that has an absolutely precise meaning, namely

dynamic, in the classical physical sense. It also has a very interesting property as an

adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense.

Try thinking of some combination that will possibly give it a pejorative meaning. It’s

impossible. Thus, I thought dynamic programming was a good name. It was something

not even a Congressman could object to.”

Dynamic Programming Overview

• Dynamic programming solves optimization problems.

– The overall strategy underlying the algorithm is that the

given problem can be solved by first solving smaller

subproblems that have the same structure. Two features

characterize these subproblems:

1.Unlike the divide-and-conquer algorithm, which relies

on subproblems being independent, dynamic

programming handles problems that have overlapping

subproblems.

2.We can apply a recursive strategy: We find an optimal

solution of each subproblem by first finding optimal

solutions for its contained subproblems.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

2

Coins Again

• We are given an unlimited number of coins of

various denominations: d1,d2, …, dm.

• We have the same objective as before: Pay out a given

sum Swith the smallest number of coins possible.

– The denomination “system” presents us with three

possibilities:

• The divalues are such that a greedy strategy can pay

out the sum Sin an optimal fashion.

• The divalues are such that a greedy strategy cannot

pay out the sum Sin an optimal fashion although such

an optimal payout does exist.

• The divalues are such that no strategy can pay out the

amount S.

(Trivial example: m = 1, di= 2 cent coin and Sis an odd amount).

A Recursive Strategy for the Coin Problem

• Find an algorithm that produces an optimal solution

for any denomination system or an indication that

no solution exists.

• Notation:

–Let coins[i] be the smallest number of coins required to

pay out the sum i.

• We assume coins[i]will be “undetermined” if no solution exists.

• Note that coins[0] = 0 (no coins needed).

– Idea behind the solution:

• Sequentially try all possibilities for the first coin paid out.

• If the coin paid out is di, we now recursively solve the change

problem for S- di.

• So, we can solve the problem recursively but with the added

constraint the we always ask for the minimum coin number.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

3

A Recursive Strategy for the Coin Problem

– These considerations lead to the following recursion:

– This recursion will be at the heart of our dynamic

programming algorithm.

– There are two approaches that can be used in working with

this recursion:

1. We can insist that the recursion defines a recursive function that

simply calls itself to get the optimal values associated with the

smaller problems. (This is not dynamic programming).

OR

2. We can consider coins to be an array that stores the optimal

values associated with the smaller problems.

– Just to eliminate it from any further discussion, we

start by showing that the first approach is

extremely bad!

[ ] 1 min{ [ ]}.

jj

d i

coins i coins i d

≤

= + −

A Recursive Function for the Coin Problem

– We start with:

• Recalling that recursive calls were used in divide and conquer we go

for the following implementation:

D&C for CP Pseudo-code 1:

function coins(i):

if (i=0) then return 0; // base case

// recursion:

min:=infinity; // Use a very large number here…

for j:=0 to m do

if (d[j] <= i) then

smaller_sol := coins(i - d[j]);

if smaller_sol < min then min := smaller_sol;

return 1 + min;

– The main program calls coins(S).

[ ] 1 min{ [ ]}.

jj

d i

coins i coins i d

≤

= + −

###### You're Reading a Preview

Unlock to view full version