Qui hoạch động

Dynamic programming
 Nội dung
Tìm hiểu về quy hoạch động (dynamic programming)
qua các ví dụ tiêu biểu:
0. Fibonacci Numbers
1. Longest common subsequence
2. Knapsack problem

Sử dụng một phần tài liệu bài giảng CS161 Stanford University

2
Khởi động: Fibonacci Numbers
• Definition:
• F(n) = F(n-1) + F(n-2), with F(1) = F(2) = 1.
• The first several are:
• 1
• 1
• 2
• 3
• 5
• 8
• 13, 21, 34, 55, 89, 144,…
• Question:
• Given n, what is F(n)?

3
 Candidate algorithm
• def Fibonacci(n):
• if n == 0, return 0
• if n == 1, return 1
• return Fibonacci(n-1) + Fibonacci(n-2)

Running time?
• T(n) = T(n-1) + T(n-2) + O(1)
• T(n) T(n-1) + T(n-2) for n
• So T(n) grows at least as fast as
the Fibonacci numbers
themselves…
• You showed in HW1 that this is
EXPONENTIALLY QUICKLY!

4
See IPython notebook for lecture 12
 What’s going on? That’s a lot of
repeated
Consider Fib(8) computation!

6 7

4 5 5 6

2 3 3 4 3 4 4 5

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

1 2 etc
0 1 1 2
0 1 0 1 1 2 0 1 0 1 0 1 1 2
5
0 1 0 1 0 1 0 1
Maybe this would be better:
8 def fasterFibonacci(n):
• F = [0, 1, None, None, …, None ]
• \\ F has length n + 1
• for i = 2, …, n:
7
• F[i] = F[i-1] + F[i-2]
• return F[n]

6 Much better running time!

1
6
0
This was an example of…

7
What is dynamic programming?
• Là một chiến lược thiết kế thuật toán (an algorithm
design paradigm)
• Các bạn đã học chiến lược chia để trị (divide-and-
conquer).
• Thường dùng để giải các bài toán tối ưu
• Ví dụ, các dạng tìm đường đi ngắn nhất
• Tính số Fibonacci không phải là bài toán tối ưu, nhưng là
một ví dụ đơn giản để thuyết minh DP

8
Elements of dynamic programming
• Optimal substructure.
• Optimal solutions to sub-problems can be used to find the
optimal solution of the original problem.
• Overlapping subproblems.
• The subproblems show up again and again

• Using these properties, we can design a dynamic

programming algorithm:
• Keep a table of solutions to the smaller problems.
• Use the solutions in the table to solve bigger problems.
• At the end we can use information we collected along the
way to find the solution to the whole thing.
9
Two ways to think about and/or
implement DP algorithms

• Top down

• Bottom up

This picture isn’t hugely relevant but I like it. 10

Bottom up approach
what we just saw.

• For Fibonacci:
• Solve the small problems first
• fill in F[0],F[1]
• Then bigger problems
• fill in F[2]
•…
• Then bigger problems
• fill in F[n-1]
• Then finally solve the real problem.
• fill in F[n]
11
Top down approach
• Think of it like a recursive algorithm.
• To solve the big problem:
• Recurse to solve smaller problems
• Those recurse to solve smaller problems
• etc..

• The difference from divide and

conquer:
• Keep track of what small problems you’ve
already solved to prevent re-solving the
same problem twice.
• Aka, “memo-ization”
12
Example of top-down Fibonacci
• define a global list F = [0,1,None, None, …, None]
• def Fibonacci(n):
• if F[n] != None:
• return F[n]
• else:
• F[n] = Fibonacci(n-1) + Fibonacci(n-2)
• return F[n]

13
 Memo-ization visualization
8

6 7

4 5 5 6

2 3 3 4 3 4 4 5

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

1 2 etc
0 1 1 2
0 1 0 1 1 2 0 1 0 1 0 1 1 2
0 1 0 1 0 1 0 1
14
C++ Implementation
int fibo(int f[], int n) {
if (f[n] >=0) return f[n];
return (f[n] = fibo(f, n-1) + f[n-2]);
}

int main() {
int n;
cin >> n;
int a[n+1];
a[0] = 0, a[1] = 1;
for (int i=2; i<=n; i++) a[i] = -1;
cout << fibo(a, n) << endl;
}

15
Nội dung
Tìm hiểu về quy hoạch động (dynamic programming)
qua các ví dụ tiêu biểu:
0. Fibonacci Numbers
1. Longest common subsequence
2. Knapsack problem

16
 Longest Common Subsequence
• How similar are these two species?

DNA: DNA:
AGCCCTAAGGGCTACCTAGCTT GACAGCCTACAAGCGTTAGCTTG

17
 Longest Common Subsequence
• How similar are these two species?

DNA: DNA:
AGCCCTAAGGGCTACCTAGCTT GACAGCCTACAAGCGTTAGCTTG
• Pretty similar, their DNA has a long common subsequence:

AGCCTAAGCTTAGCTT
18
Longest Common Subsequence
• Subsequence:
• BDFH is a subsequence of ABCDEFGH
• If X and Y are sequences, a common subsequence
is a sequence which is a subsequence of both.
• BDFH is a common subsequence of ABCDEFGH and of
ABDFGHI
• A longest common subsequence…
• …is a common subsequence that is longest.
• The longest common subsequence of ABCDEFGH and
ABDFGHI is ABDFGH.

19
Recipe for applying Dynamic Programming
• Step 1: Identify optimal substructure.
• Step 2: Find a recursive formulation for the length
of the longest common subsequence.
• Step 3: Use dynamic programming to find the
length of the longest common subsequence.
• Step 4: If needed, keep track of some additional
info so that the algorithm from Step 3 can find the
actual LCS.
• Step 5: If needed, code this up like a reasonable
person.
20
Step 1: Optimal substructure
Prefixes:

X A C G G T

Y A C G C T T A

Notation: denote this prefix ACGC by Y4

• Our sub-problems will be finding LCS’s of prefixes to X and Y.

• Let C[i,j] = length_of_LCS( Xi, Yj )
Examples: C[2,3] = 2 21
C[4,4] = 3
 • Our sub-problems will be finding
Two cases LCS’s of prefixes to X and Y.
• Let C[i,j] = length_of_LCS( Xi, Yj )
Case 1: X[i] = Y[j]
i These are
the same

Xi A C G G A
j

Yj A C G C T T A

• Then C[i,j] = 1 + C[i-1,j-1].

• because LCS(Xi,Yj) = LCS(Xi-1,Yj-1) followed by A
22
 • Our sub-problems will be finding
Two cases LCS’s of prefixes to X and Y.
• Let C[i,j] = length_of_LCS( Xi, Yj )
Case 2: X[i] != Y[j]
i These are
not the
same
Xi A C G G T
j

Yj A C G C T T A

• Then C[i,j] = max{ C[i-1,j], C[i,j-1] }.

• either LCS(Xi,Yj) = LCS(Xi-1,Yj) and T is not involved,
• or LCS(Xi,Yj) = LCS(Xi,Yj-1) and A is not involved,
• (maybe both are not involved, that’s covered by the “or”).
23
 Recursive formulation
of the optimal solution X0
Yj A C G C T T A

Case 0

Case 1 Case 2

A C G G A A C G G T
Xi Xi
Yj A C G C T T A Yj A C G C T T
24
A
LCS DP
• LCS(X, Y):
• C[i,0] = C[0,j] = 0 for all i = 0,…,m, j=0,…n.
• For i = 1,…,m and j = 1,…,n:
• If X[i] = Y[j]:
• C[i,j] = C[i-1,j-1] + 1
• Else:
• C[i,j] = max{ C[i,j-1], C[i-1,j] }
• Return C[m,n]

25
 X A C G G A

Example
Y A C T G

Y
A C T G

0 0 0 0 0

A 0

C 0

X G 0

G 0

A 0
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and26 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G

0 0 0 0 0

A 0 1 1 1 1 So the LCM of X
C 0 1 2 2 2 and Y has length 3.
X G 0 1 2 2 3

G 0 1 2 2 3

A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and27 𝑖, 𝑗 > 0
Recipe for applying Dynamic Programming
• Step 1: Identify optimal substructure.
• Step 2: Find a recursive formulation for the length
of the longest common subsequence.
• Step 3: Use dynamic programming to find the
length of the longest common subsequence.
• Step 4: If needed, keep track of some additional
info so that the algorithm from Step 3 can find the
actual LCS.
• Step 5: If needed, code this up like a reasonable
person.
28
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0

A 0 1 1 1 1

C 0 1 2 2 2

X G 0 1 2 2 3

G 0 1 2 2 3

A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and29 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0

A 0 1 1 1 1

C 0 1 2 2 2

X G 0 1 2 2 3

G 0 1 2 2 3 That 3 must have come

from the 3 above it.
A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and30 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0 • A diagonal jump means
that we found an element
A 0 1 1 1 1
of the LCS!
C 0 1 2 2 2

X G 0 1 2 2 3 This 3 came from that 2 – G

0 1 2 2 3 we found a match!
G

A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and31 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0 • A diagonal jump means
that we found an element
A 0 1 1 1 1
of the LCS!
C 0 1 2 2 2 That 2 may as well
have come from
X G 0 1 2 2 3
this other 2. G
G 0 1 2 2 3

A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and32 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0 • A diagonal jump means
that we found an element
A 0 1 1 1 1
of the LCS!
C 0 1 2 2 2

X G 0 1 2 2 3 G
G 0 1 2 2 3

A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and33 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0 • A diagonal jump means
that we found an element
A 0 1 1 1 1
of the LCS!
C 0 1 2 2 2

X G 0 1 2 2 3 C G
G 0 1 2 2 3

A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and34 𝑖, 𝑗 > 0
 X A C G G A

Example
Y A C T G

Y
A C T G
• Once we’ve filled this in,
we can work backwards.
0 0 0 0 0 • A diagonal jump means
that we found an element
A 0 1 1 1 1
of the LCS!
C 0 1 2 2 2

X G 0 1 2 2 3 A C G
G 0 1 2 2 3
This is the LCS!
A 0 1 2 2 3
0 if 𝑖 = 0 or 𝑗 = 0
𝐶 𝑖, 𝑗 = 𝐶 𝑖 − 1, 𝑗 − 1 + 1 if 𝑋 𝑖 = 𝑌 𝑗 and 𝑖, 𝑗 > 0
max 𝐶 𝑖, 𝑗 − 1 , 𝐶 𝑖 − 1, 𝑗 if 𝑋 𝑖 ≠ 𝑌 𝑗 and35 𝑖, 𝑗 > 0
Nội dung
Tìm hiểu về quy hoạch động (dynamic programming)
qua các ví dụ tiêu biểu:
0. Fibonacci Numbers
1. Longest common subsequence
2. Knapsack problem

36
 Example 2: Knapsack Problem
• We have n items with weights and values:

Item:

Weight: 6 2 4 3 11
Value:
20 8 14 13 35

• And we have a knapsack: Capacity: 10

• it can only carry so much weight:

37
Some notation

Item:

Weight: w1 w2 w3 … wn
Value: v1 v2 v3 vn

Capacity: W
38
 Item:
Weight: 6 2 4 3 11
Capacity: 10 Value: 20 8 14 13 35

• Unbounded Knapsack:
• Suppose I have infinite copies of all of the items.
• What’s the most valuable way to fill the knapsack?
Total weight: 10
Total value: 42

• 0/1 Knapsack:
• Suppose I have only one copy of each item.
• What’s the most valuable way to fill the knapsack?

Total weight: 9
Total value: 35
39
Recipe for applying Dynamic Programming
• Step 1: Identify optimal substructure.
• Step 2: Find a recursive formulation for the value of
the optimal solution.
• Step 3: Use dynamic programming to find the value
of the optimal solution.
• Step 4: If needed, keep track of some additional
info so that the algorithm from Step 3 can find the
actual solution.
• Step 5: If needed, code this up like a reasonable
person.
40
 Optimal substructure: try 2
• Sub-problems:
• 0/1 Knapsack with fewer items.

First solve the

problem with
few items
We’ll still increase the size of the knapsacks.
Then more
items

Then yet
more
items
41
Our sub-problems:
• Indexed by x and j

First j items Capacity x

K[x,j] = optimal solution for a knapsack of

size x using only the first j items. 42
Relationship between sub-problems
• Want to write K[x,j] in terms of smaller sub-problems.

First j items Capacity x

K[x,j] = optimal solution for a knapsack of

size x using only the first j items. 43
Two cases item j

• Case 1: Optimal solution for j items does not use item j.

• Case 2: Optimal solution for j items does use item j.

First j items Capacity x

K[x,j] = optimal solution for a knapsack of

size x using only the first j items. 44
 Two cases item j

• Case 1: Optimal solution for j items does not use item j.

Capacity x
Value V
First j items Use only the first j items

What lower-indexed problem

should we solve to solve this
problem?
1 min think; (wait) 1 min share

45
 Two cases item j

• Case 1: Optimal solution for j items does not use item j.

Capacity x
Value V
First j items Use only the first j items

• Then this is an optimal solution for j-1 items:

Capacity x
Value V 46
First j-1 items Use only the first j-1 items.
 Two cases item j

• Case 2: Optimal solution for j items uses item j.

Weight wj
Value vj Capacity x
Value V
First j items Use only the first j items

What lower-indexed problem

should we solve to solve this
problem?
1 min think; (wait) 1 min share

47
 Two cases item j

• Case 2: Optimal solution for j items uses item j.

Weight wj
Value vj Capacity x
Value V
First j items Use only the first j items
• Then this is an optimal solution for j-1 items and a
smaller knapsack:

Capacity x – wj
Value V – vj
First j-1 items Use only the first j-148items.
Recursive relationship
• Let K[x,j] be the optimal value for:
• capacity x,
• with j items.

K[x,j] = max{ K[x, j-1] , K[x – wj, j-1] + vj }

Case 1 Case 2

• (And K[x,0] = 0 and K[0,j] = 0).

49
Bottom-up DP algorithm
• Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n
• for x = 1,…,W:
• for j = 1,…,n: Case 1
• K[x,j] = K[x, j-1]
• if wj x: Case 2
• K[x,j] = max{ K[x,j], K[x – wj, j-1] + vj }
• return K[W,n]

Running time O(nW)

50
 • Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n

Example • for x = 1,…,W:

• for j = 1,…,n:
• K[x,j] = K[x, j-1]
• if wj ≤ x:
x=0 x=1 x=2 x=3 • K[x,j] = max{ K[x,j],
K[x – wj, j-1] + vj }
0 0 0 0 • return K[W,n]
j=0

0
j=1

0
j=2

0
j=3

Item:
current relevant Weight: 1 2 3
entry previous entry Value: 1 4 6 Capacity:
51 3
 • Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n

Example • for x = 1,…,W:

• for j = 1,…,n:
• K[x,j] = K[x, j-1]
• if wj ≤ x:
x=0 x=1 x=2 x=3 • K[x,j] = max{ K[x,j],
K[x – wj, j-1] + vj }
0 0 0 0 • return K[W,n]
j=0

0 0
j=1

0
j=2

0
j=3

Item:
current relevant Weight: 1 2 3
entry previous entry Value: 1 4 6 Capacity:
52 3
 • Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n

Example • for x = 1,…,W:

• for j = 1,…,n:
• K[x,j] = K[x, j-1]
• if wj ≤ x:
x=0 x=1 x=2 x=3 • K[x,j] = max{ K[x,j],
K[x – wj, j-1] + vj }
0 0 0 0 • return K[W,n]
j=0

0 1
j=1

0
j=2

0
j=3

Item:
current relevant Weight: 1 2 3
entry previous entry Value: 1 4 6 Capacity:
53 3
 • Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n

Example • for x = 1,…,W:

• for j = 1,…,n:
• K[x,j] = K[x, j-1]
• if wj ≤ x:
x=0 x=1 x=2 x=3 • K[x,j] = max{ K[x,j],
K[x – wj, j-1] + vj }
0 0 0 0 • return K[W,n]
j=0

0 1 1
j=1

0 1 4
j=2

0 1
j=3

Item:
current relevant Weight: 1 2 3
entry previous entry Value: 1 4 6 Capacity:
54 3
 • Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n

Example • for x = 1,…,W:

• for j = 1,…,n:
• K[x,j] = K[x, j-1]
• if wj ≤ x:
x=0 x=1 x=2 x=3 • K[x,j] = max{ K[x,j],
K[x – wj, j-1] + vj }
0 0 0 0 • return K[W,n]
j=0

0 1 1
j=1

0 1 4
j=2

0 1 4
j=3

Item:
current relevant Weight: 1 2 3
entry previous entry Value: 1 4 6 Capacity:
55 3
 • Zero-One-Knapsack(W, n, w, v):
• K[x,0] = 0 for all x = 0,…,W
• K[0,i] = 0 for all i = 0,…,n

Example • for x = 1,…,W:

• for j = 1,…,n:
• K[x,j] = K[x, j-1]
• if wj ≤ x:
x=0 x=1 x=2 x=3 • K[x,j] = max{ K[x,j],
K[x – wj, j-1] + vj }
0 0 0 0 • return K[W,n]
j=0

0 1 1 1
j=1

0 1 4 5
j=2
So the optimal solution is to
0 1 4 6 put one watermelon in your
j=3 knapsack!

Item:
current relevant Weight: 1 2 3
entry previous entry Value: 1 4 6 Capacity:
56 3
What have we learned?

• Paradigm in algorithm design.

• Uses optimal substructure
• Uses overlapping subproblems
• Can be implemented bottom-up or top-down.
• It’s a fancy name for a pretty common-sense idea:

57
Why “dynamic programming” ?
• Programming refers to finding the optimal “program.”
• as in, a shortest route is a plan aka a program.
• Dynamic refers to the fact that it’s multi-stage.
• But also it’s just a fancy-sounding name.

Manipulating computer code in an action movie?

58
Why “dynamic programming” ?
• Richard Bellman invented the name in the 1950’s.
• At the time, he was working for the RAND
Corporation, which was basically working for the
Air Force, and government projects needed flashy
names to get funded.
• From Bellman’s autobiography:
• “It’s impossible to use the word, dynamic, in the
pejorative sense…I thought dynamic programming was
a good name. It was something not even a
Congressman could object to.”

59