Optimization

Dynamic Programming
Dynamic Programming Intro

Dynamic programming. Break up a problem into

a series of overlapping sub-problems, and build
up solutions to larger and larger sub-problems.

Algorithmic method typically used to find an

optimal solution

2
Example: Interval Scheduling

• Weighted interval scheduling problem.

– Job j starts at sj, finishes at fj, and has weight or
value vj .
– Two jobs compatible if they don't overlap.
– Goal: find maximum weight subset of mutually
compatible jobs.

3
Interval Scheduling

Note: LPs are not a good model because they are

fractional

4
 Example: Interval Scheduling
Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn .

Def. p(j) = largest index i < j such that job i is compatible

with j.

Ex: p(8) = 5, p(7) = 3, p(2) = 0.

5
 Example: Interval Scheduling
Notation. OPT(j) = value of optimal solution to the problem consisting of job
requests 1, 2, ..., j.

Case 1: The optimal solution OPT selects job j.

- collect profit vj
- can't use incompatible jobs { p(j) + 1, p(j) + 2, ..., j - 1 }
- must include optimal solution to problem consisting of remaining
compatible jobs 1, 2, ..., p(j)

Case 2: OPT does not select job j.

- must include optimal solution to problem consisting of remaining
compatible jobs 1, 2, ..., j-1

# 0 if j = 0
OPT( j) = $
%max { v j + OPT( p( j)), OPT( j −1) } otherwise

6
€
Brute Force Approach

7
Brute Force Approach

Observation. Recursive algorithm fails spectacularly because of

redundant sub-problems Þ exponential time algorithm.

8
Memoization

• Memoization. Store results of each sub-

problem in a cache; lookup as needed.

9
Dynamic Programming Overview

• The problem structure is divided into stages

• Each stage has a number of states associated with it
• Making decisions at one stage transforms one state of
the current stage into a state in the next stage.
• Given the current state, the optimal decision for each of
the remaining states does not depend on the previous
states or decisions. This is known as the principle of
optimality for dynamic programming.
• The principle of optimality allows to solve the problem
stage by stage recursively.

10
States

• Each stage has a number of states associated

with it. Depending what decisions are made in
one stage, the system might end up in different
states in the next stage.
– For interval selection our state depended on where
the last interval ended
• States are problem specific

11
Decisions

Making decisions at one stage transforms one

state of the current stage into a state in the next
stage.
In the interval selection problem the decision is to
choose the interval or not

12
Optimal Policy and Principal of Optimality

The goal of the solution procedure is to find an optimal

policy for the overall problem, i.e., an optimal policy
decision at each stage for each of the possible states.
Given the current state, the optimal decision for each of
the remaining states does not depend on the previous
states or decisions. This is known as the principle of
optimality for dynamic programming.
For example, in the interval selection problem the
principle works as follows: the optimal route solution for
intervals 1, …, j does not depend on intervals starting
after j
A system can be formulated as a dynamic programming
problem only if the principle of optimality holds for it.
13
Constructing the Solution

The principle of optimality allows to solve the problem

stage by stage recursively.
The solution procedure first finds the optimal policy for the
last stage. The solution for the last stage is normally
trivial.
Then a recursive relationship is established which
identifies the optimal policy for stage t, given that stage
t+1 has already been solved.
When the recursive relationship is used, the solution
procedure starts at the end and moves backward stage
by stage until it finds the optimal policy starting at the
initial stage.
14
Example: Coins

• To find the minimum number of US coins to make any amount,

the greedy method always works
– At each step, just choose the largest coin that does not overshoot the
desired amount: 31¢=>25
• The greedy method would not work if we did not have 5¢ coins
– For 31 cents, the greedy method gives seven coins (25+1+1+1+1+1+1),
but we can do it with four (10+10+10+1)
• The greedy method also would not work if we had a 21¢ coin
– For 63 cents, the greedy method gives six coins (25+25+10+1+1+1), but
we can do it with three (21+21+21)
• How can we find the minimum number of coins for any given
coin set?

15
Example: Coins

• For the following examples, we will assume

coins in the following denominations:
1¢ 5¢ 10¢ 21¢ 25¢

• Say we want to make change for some value K

using the minimum number of coins

• The solution we will derive extends to all sets of

coins, so long as the 1¢ coin is in the set
16
Example: Coins

• To make K cents:
– If there is a K-cent coin, then that one coin is the minimum
– Otherwise, for each value i < K,
• Find the minimum number of coins needed to make
i cents
• Find the minimum number of coins needed to make
K - i cents
– Choose the i that minimizes this sum
• This algorithm can be viewed as brute force
– This solution is very recursive
– It requires exponential sub-problems

17
Example: Coins

• We can reduce the problem recursively by

choosing the first coin, and solving for the
amount that is left
• For 63¢:
– One 1¢ coin plus the best solution for 62¢
– One 5¢ coin plus the best solution for 58¢
– One 10¢ coin plus the best solution for 53¢
– One 21¢ coin plus the best solution for 42¢
– One 25¢ coin plus the best solution for 38¢
• Choose the best solution from among the 5
given above
18
Example: Coins

• Use Memoization: Solve first for one cent, then two cents, then
three cents, etc., up to the desired amount
– Save each answer

• OPT(K’): the minimum number of coins to make change for K’

– OPT(K’) minC { 1 + OPT(K’-C)} where C is over all possible coins

19
In-Class Problem

• Problem input is a number n

• Can perform operations
– Divide by 3 if the number is divisible by 3
– Divide by 2 if the number is divisible by 2
– Subtract 1

• Find the minimum number of operations until

the number is 1
• Give a DP to solve this problem
20
Shortest Path Example

• Shortest Path Problem: Given a network find

the shortest path between two vertices s and t

• Previously we saw an LP approach

• Today a dynamic programming approach is

presented
– There are many approaches to solve this problem

21
Motivating Example

• Nodes represent agents in a financial setting

and cvw is cost of transaction in which we buy
from agent v and sell immediately to w.
– For example, thing of exchanging currencies
– Negative weights are not allowed (but we could)
2 10 3
9
s
18
6 16 6
6
30 4 19
11
15 5
8
6
20 16

7 t
44
22
Breaking into SubProblems

• OPT(i, v) = length of shortest v-t path P using at

most i edges for some vertex v.

– Case 1: P uses at most i-1 edges.

• OPT(i, v) = OPT(i-1, v)

– Case 2: P uses exactly i edges.

• if (v, w) is first edge, then OPT uses (v, w), and then
selects best w-t path using at most i-1 edges

23
Breaking into Subproblems

ì 0 if v = t , ¥ otherwise if i = 0
ï
OPT (i,v) = í ì ü
miníOPT (i - 1,v), min {OPT (i - 1,w) + cvw }ý otherwise
ïî î ( v ,w )ÎE þ

24
Knapsack Problem

• Given a set of n boxes where

– Each item i has a weight wi
– Each item has a profit pi

• Select a set of items to ship in a single truck

that can hold a weight of W

• How should we choose items?

– Items cannot be fractionally chosen
25
Knapsack Dynamic Program

• Sort items arbitrarily 1, 2, …, n

• OPT(i, W’): The most profit that can be
obtained using items 1,2,…,i whose total weight
is W’

• Want to know OPT(n,W)

• Can we define this recursively?

26
Define Recusviely

• OPT(i, W’)

• What are the possible choices to make

concerning the ith item

27
Define Recusviely

• OPT(i, W’) = max{OPT(i-1, W’), OPT(i-1, W’ –si)+pi}

– Either the solution takes the ith item or not

28
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3: (4,5)
2 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3: (4,5)
2 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3: (4,5)
2 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3: (4,5)
2 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4 5
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4 5 7
4 0

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4 5 7
4 0 0 3 4 5

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4 5 7
4 0 0 3 4 5 7

OPT(i, W’) = max{OPT(i-1, W’),

OPT(i-1, W’ –si)+pi}
Example Knapsack

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4 5 7
4 0 0 3 4 5 7

Done!
How do we find items?
Backtracking

Items
(weight,profit):
i/w 0 1 2 3 4 5
1: (2,3)
0 0 0 0 0 0 0
2: (3,4)
1 0 0 3 3 3 3 3: (4,5)
2 0 0 3 4 4 7 4: (5,6)
3 0 0 3 4 5 7
4 0 0 3 4 5 7
Solving the Problem

1) Fill out the dynamic programming table for

the following knapsack problem.
2) Trace back through the table to find the items

Item # wi pi W=20
1 2 3
2 4 5
3 5 8
4 3 4
5 9 10 47
Solving the Problem

1) Fill out the dynamic programming table for

the following knapsack problem.
2) Trace back through the table to find the items

Item # wi pi W=20
1 2 3
2 4 5 Solution for first
3 5 8 four items not
4 3 4 subset of the
solution for all 5!
5 9 10 48
In-Class Problem

• You are driving from Pittsburgh to San Francisco. You fixed your
driving route. Along the way you have to stop for gas. There
are n gas stations x1, x2, …, xn. It takes costs ci to fill up at
station xi regardless of how much gas you need.
• Assume the stations are ordered according to the order you see
them on your route.
• Your car drives 300 miles before you need to gas and you start
at gas station x1.
• di is the distance between stations xi and xi+1
• Design a dynamic program to decide which stations to fill at to
minimize the cost.

49