Algorithms design

Techniques

3- Dynamic
Programming

1
 Dynamic
Programming
• Dynamic programming approach for
the algorithm design solves the
problem by combining the solution to
subproblems.
• DP is used in optimization problems
(minimizing or maximizing).
• Like divide and conquer, DP solves
problems by combining solutions to
subproblems.
• Unlike divide and conquer, subproblems
are not independent.
2
 subproblems may share
Steps in Dynamic Programming

1. Characterize structure of an optimal solution.

2. Define value of optimal solution recursively.

3. Compute the value of optimal solution in a

bottom-up fashion.

4. Construct an optimal solution from computed

values.

3
Meaning of bottom-up

1. Start with the smallest subproblems.

2. Combining theirs solutions obtain the

solutions to subproblems of
increasing size.
3. Until arrive at the solutions of the

original problem.
4
In dynamic programming we usually reduce

time by increasing the amount of space.

We solve the problem by solving
subproblems of increasing size and saving
each optimal solution in a table (usually).
The table is then used for finding the optimal

solution to larger problems.

Time is saved since each subproblem is

5
solved only once.
 Elements of Dynamic
Programming
Optimal Substructure

An optimal solution to a problem contains within it

an optimal solution to subproblems

Optimal solution to the entire problem is build in a

bottom-up manner from optimal solutions to

subproblems
Overlapping Subproblems

If a recursive algorithm revisits the same

subproblems over and over  the problem has

6 overlapping subproblems
 Fibonacci Numbers
Fib(5)
+

Fib(4) Fib(3)
+ +

Fib(3) Fib(2) Fib(2) Fib(1)

+ + +

Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)

+

Fib(1) Fib(0)

7
 0-1 Knapsack problem
dynamic programming approach

We can do better with an algorithm

based on dynamic programming

We need to carefully identify the

subproblems

8
Defining a Subproblem

Given a knapsack with maximum capacity

W, and a set S consisting of n items

Each item i has some weight wi and benefit

value bi (all wi and W are integer values)

Problem: How to pack the knapsack to

achieve maximum total value of packed

items?
9
dynamic programming
approach
If items are labeled 1,2,....,n, then we will be

compute V[k, w], to find an optimal solution for

={items labeled 1, 2, .. k} in a knapsack of size w.

10
 Recursive Formula for
subproblems
The subproblem will then be to
compute V[k, w], i.e., to find an optimal
solution for Sk = {items labeled 1, 2, ..
k} in a knapsack of size w
Assuming knowing V[i, j], where i=0,1,
2, … k-1, j=0,1,2, …w, how to derive
V[k, w]?
We construct a matrix B
[0……..n,0…..W].
11
 Recursive Formula for
subproblems (continued)
• Recursive formula for subproblems:
 V [ k  1, w] if wk  w
V [ k , w] 
max{V [ k  1, w], V [ k  1, w  wk ]  bk }

It means, that the best subset of Sk that has total

weight w is:
1) the best subset of Sk-1 that has total weight  w,
or
2) the best subset of Sk-1 that has total weight  w-wk
plus the item k

12
 0-1 Knapsack Algorithm
for w = 0 to W
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 0 to W
if wi <= w // item i can be part of the
solution
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
14
 Running time
for w = 0 to W
O(W)
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n Repeat n times
for w = 0 to W O(W)
< the rest of the code >
What is the running time of this
O(n*W) ? algorithm

15
 Example
Let’s run our algorithm on the following data:
n = 4 (# of elements)
W = 5 (max weight)
:Elements (weight, benefit)
)5,6( ,)4,5( ,)3,4( ,)2,3(

16
 Example (2)
i\W 0 1 2 3 4 5
0 0 0 0 0 0 0
1
2
3
4

for w = 0 to W
V[0,w] = 0

17
 Example (3)
i\W 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0
2 0
3 0
4 0

for i = 1 to n
V[i,0] = 0

18
 :Items
Example (4) )2,3( :1
)3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 i=1
2 0 bi=3
3 0 wi=2
4 0 w=1
if wi <= w // item i can be part of the solution w-wi =-1
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
19
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (5) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 i=1
2 0 bi=3
3 0
wi=2
4 0
if wi <= w // item i can be part of the solution
w=2
if bi + V[i-1,w-wi] > V[i-1,w] w-wi =0
V[i,w] = bi + V[i-1,w- wi]
else
20
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (6) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 i=1
2 0 bi=3
3 0 wi=2
4 0
w=3
if wi <= w // item i can be part of the solution
w-wi =1
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
21
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (7) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 i=1
2 0 bi=3
3 0 wi=2
4 0
w=4
if wi <= w // item i can be part of the solution
w-wi =2
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
22
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (8) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=1
2 0 bi=3
3 0 wi=2
4 0 w=5
if wi <= w // item i can be part of the solution w-wi =3
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
23
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (9) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=2
2 0 0 bi=4
3 0 wi=3
4 0 w=1
if wi <= w // item i can be part of the solution w-wi =-2
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
24
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (10) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=2
2 0 0 3 bi=4
3 0 wi=3
4 0 w=2
if wi <= w // item i can be part of the solution w-wi =-1
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
25 V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // w > w
 :Items
)2,3( :1
Example (11) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=2
2 0 0 3 4 bi=4
3 0 wi=3
4 0 w=3
if wi <= w // item i can be part of the solution w-wi =0
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
26
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (12) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=2
2 0 0 3 4 4 bi=4
3 0
wi=3
4 0
w=4
if wi <= w // item i can be part of the solution
if bi + V[i-1,w-wi] > V[i-1,w]
w-wi =1
V[i,w] = bi + V[i-1,w- wi]
else
27
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (13) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=2
2 0 0 3 4 4 7 bi=4
3 0
wi=3
4 0
w=5
if wi <= w // item i can be part of the solution
w-wi =2
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
28 V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // w > w
 :Items
)2,3( :1
Example (14) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=3
2 0 0 3 4 4 7 bi=5
3 0 0 3 4 wi=4
4 0
w= 1..3
if wi <= w // item i can be part of the solution
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
29
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (15) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=3
2 0 0 3 4 4 7 bi=5
3 0 0 3 4 5 wi=4
4 0
w= 4
if wi <= w // item i can be part of the solution
w- wi=0
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
30
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (16) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=3
2 0 0 3 4 4 7 bi=5
3 0 0 3 4 5 7
wi=4
4 0
if wi <= w // item i can be part of the solution
w= 5
if bi + V[i-1,w-wi] > V[i-1,w] w- wi=1
V[i,w] = bi + V[i-1,w- wi]
else
31
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (17) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=4
2 0 0 3 4 4 7 bi=6
3 0 0 3 4 5 7
wi=5
4 0 0 3 4 5
w= 1..4
if wi <= w // item i can be part of the solution
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
32
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 :Items
)2,3( :1
Example (18) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=4
2 0 0 3 4 4 7 bi=6
3 0 0 3 4 5 7 wi=5
4 0 0 3 4 5 7
w= 5
if wi <= w // item i can be part of the solution
w- wi=0
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
33
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w] // wi > w
 Comments
This algorithm only finds the max

possible value that can be carried

in the knapsack
i.e., the value in V[n,W]

To know the items that make this

maximum value
34
How to find actual Knapsack
Items?
All of the information we need is in the

table.
V[n,W] is the maximal value of items

that can be placed in the Knapsack.

Let i=n and k=W
if V[i,k]  V[i1,k] then
mark the ith item as in the knapsack
i = i1, k = k-wi
35
else
i = i1 // Assume the ith item is not in
 :Items
)2,3( :1
Finding the Items )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3
i=4
2 0 0 3 4 4 7
k= 5
3 0 0 3 4 5 7
bi=6
4 0 0 3 4 5 7
wi=5
i=n, k=W
while i,k > 0 V[i,k] = 7
if V[i,k]  V[i1,k] then V[i1,k] =7
mark the ith item as in the knapsack
i = i1, k = k-wi
else
36
i = i1
 :Items
)2,3( :1
Finding the Items (2) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3
2 0 0 3 4 4 7 i=4
k= 5
3 0 0 3 4 5 7
bi=6
4 0 0 3 4 5 7
wi=5
i=n, k=W
while i,k > 0 V[i,k] = 7
if V[i,k]  V[i1,k] then V[i1,k] =7
mark the ith item as in the knapsack
i = i1, k = k-wi
else
37
i = i1
 :Items
)2,3( :1
Finding the Items (3) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3
i=3
2 0 0 3 4 4 7
k= 5
3 0 0 3 4 5 7
bi=5
4 0 0 3 4 5 7
wi=4
i=n, k=W
while i,k > 0 V[i,k] = 7
if V[i,k]  V[i1,k] then V[i1,k] =7
mark the ith item as in the knapsack
i = i1, k = k-wi
else
38
i = i1
 :Items
)2,3( :1
Finding the Items (4) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3 i=2
2 0 0 3 4 4 7 k= 5
3 0 0 3 4 5 7 bi=4
4 0 0 3 4 5 7 wi=3
i=n, k=W V[i,k] = 7
while i,k > 0 V[i1,k] =3
if V[i,k]  V[i1,k] then
mark the ith item as in the knapsack
k  wi=2
i = i1, k = k-wi
else
39 i = i 1
 :Items
)2,3( :1
Finding the Items (5) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
1 0 0 3 3 3 3
i=1
2 0 0 3 4 4 7
k= 2
3 0 0 3 4 5 7
bi=3
4 0 0 3 4 5 7
wi=2
i=n, k=W
while i,k > 0 V[i,k] = 3
if V[i,k]  V[i1,k] then V[i1,k] =0
mark the ith item as in the knapsack k  wi=0
i = i1, k = k-wi
else
40 i = i 1
 :Items
)2,3( :1
Finding the Items (6) )3,4( :2
)4,5( :3
i\W 0 1 2 3 4 5 )5,6( :4
0 0 0 0 0 0 0
i=0
1 0 0 3 3 3 3
k= 0
2 0 0 3 4 4 7
3 0 0 3 4 5 7
4 0 0 3 4 5 7
The optimal
i=n, k=W
knapsack
while i,k > 0
if V[i,k]  V[i1,k] then should contain
mark the nth item as in the knapsack {1, 2}
i = i1, k = k-wi
else
41 i = i 1