Lecture 15: 2D Dynamic Programming
2D because we use two-dimensional array to store solutions
and a knapsack with capacity . Goal: Find satisfying
Copyright By PowCoder代写 加微信 powcoder
The 0/1 Knapsack Problem
Input: A set of items,
where item has weight and value
that maximizes
Recall: Greedy doesn’t provide optimal solution.
The Recurrence
First Attempt Definition: Let be the largest obtainable value for a knapsack with capacity .
First Attempt Recurrence:
If Optimal Solution for knapsack of size w chooses item i, remainder of optimal solution is optimal solution for subproblem of filling knapsack of size 𝑤 − 𝑤 (1D solution coin denominations)
WRONG: This may pick the same item more than once! Non-legal Solution!
New 2D definition: Let be the largest obtained value for a knapsack
with capacity
Recurrence:
, choosing ONLY from the first items.
Doesn’t choose i
Input: A set of 𝒏 items; item 𝒊 has weight 𝒘𝒊 and value 𝒗𝒊; a knapsack with capacity 𝑾. Goal: Find 𝑥, … , 𝑥 ∈ {0,1} such that ∑ 𝑥𝑤 ≤ 𝑊 and ∑ 𝑥𝑣 is maximized.
Subproblem:
is the largest obtained value for
knapsack with capacity , choosing ONLY from items 1 … i.
Recurrence:
FindOrderforfilling intable: Fori=1ton
For w = 1 to W
Required Solution:
DP is 2-Dimensional (2 variables) and not 1-D.
The Algorithm
let 𝑉[0..𝑛,0..𝑊] be a new 2D array of all 0 for 𝑖←1 to 𝑛 do
for 𝑤←1 to 𝑊 do
if 𝑤[𝑖]≤𝑤 and 𝑣[𝑖]+𝑉[𝑖−1,𝑤−𝑤[𝑖]]>𝑉 𝑖−1,𝑤 then
𝑉 𝑖,𝑤 ←𝑣[𝑖]+𝑉[𝑖−1,𝑤−𝑤[𝑖]]
𝑉𝑖,𝑤 ←𝑉[𝑖−1,𝑤] return 𝑉[𝑛,𝑊]
Running time: Space:
improved to
, but can be
10 40 30 50 5463
𝑉[𝑖,w] 0 1 2 3 4 5 6 7 8 9 10 𝑖=000000000000
1 0 0 0 0 0 10 10 10 10 10 10
2 0 0 0 0 40 40 40 40 40 50 50
3 0 0 0 0 40 40 40 40 40 50 70
4 0 0 0 50 50 50 50 90 90 90 90
Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in keep[i,j]
let 𝑉[0..𝑛,0 ..𝑊] and 𝑘𝑒𝑒𝑝 0..𝑛,0..𝑊 be a new array of all 0 for 𝑖←1 to 𝑛 do
for 𝑤←1 to 𝑊 do
if 𝑤[𝑖]≤𝑤 and 𝑣[𝑖]+𝑉[𝑖−1,𝑤−𝑤[𝑖]]>𝑉 𝑖−1,𝑤 then
𝑉𝑖,𝑤 ←𝑣𝑖 +𝑉𝑖−1,𝑤−𝑤𝑖
𝑘𝑒𝑒𝑝𝑖,𝑤 ←1
for 𝑖←𝑛 downto 1 do
if 𝑘𝑒𝑒𝑝𝑖,𝐾 =1 then print 𝑖
𝐾 ← 𝐾 − 𝑤[𝑖]
𝑉𝑖,𝑤 ←𝑉𝑖−1,𝑤
𝑘𝑒𝑒𝑝𝑖,𝑤 ←0
Running time:
Space: , cannot be improved to due to the array.
Problem: Given two sequences ,wesaythat
of and if forall and
isacommonsubsequence
Longest Common Subsequence
The goal is to find the longest common subsequence of
:ABAC BDAB : BDCAB A :BCBA
The Recurrence
Observation: The problem is equivalent to finding the maximum matching between and such that matched pairs don’t cross.
:ABAFCBDAB :BDCAGGBA
: B C B A isasolution
The Recurrence
Observation: The problem is equivalent to finding the maximum matching between and such that matched pairs don’t cross.
:ABAFCBDAB :BDCAGGBA
: B C B A isasolution
’: B A B A is another legal solution
The Recurrence
Def: is length of the longest common subsequence of and . Observations: The problem is equivalent to finding the maximum matching
between and such that matched pairs don’t cross.
The recurrence:
Case1:If ,thenwematch and .
Case 2: If , then either or is not matched.
Optimal solution reduces to either or .
0 if 𝑖 = 0 or 𝑗 = 0
𝑐 𝑖, 𝑗 = 𝑐 𝑖 − 1, 𝑗 − 1 + 1 if 𝑖, 𝑗 > 0 and 𝑥 = 𝑦
max{𝑐 𝑖,𝑗−1 ,𝑐 𝑖−1,𝑗 } if𝑖,𝑗>0and𝑥 ≠𝑦
The Recurrence and Algorithm
let 𝑐[0..𝑚,0..𝑛] and 𝑏[0..𝑚,0..𝑛] be new arrays of all 0 for 𝑖←1 to 𝑚
for 𝑗←1 to 𝑛 if𝑥=𝑦 then
𝑐𝑖,𝑗 ←𝑐[𝑖−1,𝑗−1]+1
else if 𝑐[𝑖 − 1,𝑗] ≥ 𝑐[𝑖,𝑗 − 1] then
𝑐 𝑖,𝑗 ←𝑐[𝑖−1,𝑗]
MATCH 𝑥,𝑦
𝑥 not matched
𝑦 not matched
𝑏 𝑖, 𝑗 ← ” ← “ Print-LCS(𝑏, 𝑚, 𝑛)
𝑐𝑖,𝑗 ←𝑐[𝑖,𝑗−1]
Running time:
Space: , can be improved to if we only need to return the optimal length.
Reconstruct the Optimal Solution
Print-LCS(𝑏, 𝑖, 𝑗):
if 𝑖=0 or 𝑗=0 then return if 𝑏[𝑖,𝑗]=”↖“ then
Print-LCS(𝑏, 𝑖 − 1, 𝑗 − 1)
else if 𝑏[𝑖,𝑗]=”↑”
Print-LCS(𝑏, 𝑖 − 1, 𝑗) else Print-LCS(𝑏,𝑖,𝑗−1)
Value of b[i,j] indicates whether ↖:𝑥,𝑦 matched:
then write 𝑥 and return LCS (i-1,j-1) 𝑥 not matched
skip 𝑥 and return LCS (i-1,j)
𝑦 not matched
skip 𝑦 and return LCS (i,j-1)
Problem: Given two strings find their longest common substring there are indices and with
and , we wish to , that is, the largest for which
Longest Common Substring
X : DEADBEEF
Y : EATBEEF
Z : BEEF //pick the longest contiguous substring
Note: Brute-force algorithm takes time.
Different from LCS problem because, in this problem, letters have to be together.
The Recurrence
Def: the length of the longest common substring of . (Does this work?)
Def: the length of the longest common substring of that ends at and .
Q: Wait, are we changing the problem?
A: Yes, but it’s OK. Optimal solution to the original is just
Recurrence:
If , then there can’t be a common substring ending at
, then the LCS of and is just the LCS of and
The Algorithm
let 𝑑[0..𝑚,0..𝑛] be a new array of all 0 𝑙 ←0,𝑝 ←0
for 𝑖←1 to 𝑚
for 𝑗←1 to 𝑛 if𝑥=𝑦 then
𝑑 𝑖,𝑗 ←𝑑[𝑖−1,𝑗−1]+1 if𝑑𝑖,𝑗>𝑙 then
𝑙 ← 𝑑 𝑖, 𝑗
𝑝 ← 𝑖 for 𝑖←𝑝−𝑙+1 to 𝑝
Note: For this problem, reconstructing the optimal solution just needs the location of the LCS.
Running time:
Space: but can be improved to .
Exercise on Edit Distance
Given two strings s and t, the edit distance edit(s,t) is the smallest
number of following edit operations to turn s into t: Insertion: add a letter
Deletion: remove a letter
Substitution: replace a character with another one.
Example: s = abode and t = blog. Then, edit(s,t) = 4 operations Start from abode
1 delete a bode
2 insert l after b blode
3 delete d bloe
4 substitute e with g blog
Impossible to do so with at most 3 operations.
Exercise on Edit Distance (cont)
Let s and t be two strings with lengths m and n, respectively. 1 If m = 0, then edit(s,t) = n.
2 If n = 0, then edit(s,t) = m.
3 If m > 0, n > 0, and s[m] = t[n], then edit(s,t) is min(
1 + edit(s[1..m],t[1..n − 1]) 1 + edit(s[1..m − 1],t[1..n]) edit(s[1..m − 1],t[1..n − 1]))
Explanation of Case 3
i] Delete t[n], and use the least number of edit operations to change s[1..m] into t[1..n − 1]. The total number of edit operations is therefore 1 + edit(s[1..m],t[1..n − 1]). (example: s:abc, t=abcc)
ii] Delete s[m], and use the least number of edit operations to change s[1..m − 1] into t[1..n]. The total number of edit operations is therefore 1 + edit(s[1..m − 1],t[1..n]). (example: s:abcc, t=abc)
iii] Simply change s[1..m − 1] into t[1..n − 1]. The total number of edit operations is therefore edit(s[1..m − 1],t[1..n − 1]).
Exercise on Edit Distance (cont2)
Let s and t be two strings with lengths m and n, respectively. 4 If m > 0, n > 0, and s[m] ≠ t[n], then edit(s,t) is min(
1 + edit(s[1..m],t[1..n − 1])
1 + edit(s[1..m − 1],t[1..n])
1 + edit(s[1..m − 1],t[1..n − 1]))
Lets store edit(i,j) in an array E[i,j]. Then E[i,j]=min( 1 + E[i,j-1]
1 + E[i-1,j]
E[i-1,j-1] if s[i] = t[j], or E[i-1,j-1]+1 if s[i] ≠ t[j])
DP Algorithm for filling array E
1 Fill in row 0 and column 0.
2 Fill in the cells of row 1 from left to right. 3 Fill in the cells of row 2 from left to right. 4 …
5 Fill in the cells of row m from left to right.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com