Report

Dynamic Programming Day 3: Examples Longest Common Subsequence • Given two sequences of characters A, B • Find the longest sequence C such that C is a subsequence of A as well as of B • Example: – ABCDGH – ZBAEDH – Length of LCS = 3 Longest Common Subsequence Iterative DP -- A B C D G H -- 0 0 0 0 0 0 0 Z 0 0 B 0 0 A 0 1 E 0 1 D 0 1 A 0 1 Longest Common Subsequence Iterative DP -- A B C D G H -- 0 0 0 0 0 0 0 Z 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 A 0 1 1 1 1 1 1 E 0 1 1 1 1 1 1 D 0 1 1 1 2 2 2 H 0 1 1 1 2 2 3 Longest Common Subsequence Length (UVA 10405) – Iterative DP int a[1010][1010]; int main() { ... memset(a, 0, sizeof(a)); for(int i = 0; i < str1.size(); i++) { for(int j = 0; j < str2.size(); j++) { if (str1[i] == str2[j]) a[i+1][j+1] >?= a[i][j] + 1; a[i+1][j+1] >?= a[i+1][j]; a[i+1][j+1] >?= a[i][j+1]; } } cout << a[str1.size()][str2.size()] << endl; } Longest Common Subsequence Length (UVA 10405) - Memoization int lcs(int a, int b) { if (cache[a][b] >= 0) return cache[a][b]; if (a == str1.size() || b == str2.size()) return 0; int ret = 0; if (str1[a] == str2[b]) ret = 1 + lcs(a+1, b+1); return cache[a][b] = max(ret, lcs(a, b + 1), lcs(a + 1, b)); } Longest Common Subsequence Path Extraction (UVA 531) • It is wonderful that we know how to compute the length of the longest common subsequence, BUT: • How do we find out what the subsequence really is? • In a more general case, we often need to find out not only the “quality” of the optimal solution, but also what it is • How to do this? Let’s look at our DP table again. Longest Common Subsequence Path Extraction (UVA 531) -- A B C D G H -- 0 0 0 0 0 0 0 Z 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 A 0 1 1 1 1 1 1 E 0 1 1 1 1 1 1 D 0 1 1 1 2 2 2 H 0 1 1 1 2 2 3 Longest Common Subsequence Path Extraction (UVA 531) • We can trace our way back through the DP table: vector<string> path; int i = str1.size() - 1, j = str2.size() - 1; while (i >= 0 && j >= 0) { if (a[i+1][j+1] == a[i][j+1]) i--; else if (a[i+1][j+1] == a[i+1][j]) j--; else { path.push_back(str1[i]); i--; j--; } } reverse(path.begin(), path.end()); Critical Mass (UVA 580) • 3 types of boxes: lead and uranium • Stacking boxes on top of each other • Stack is dangerous if 3 or more uranium boxes on top of each other • How many dangerous stacks of height H are there? • For example, 3 dangerous stacks if H = 4: – LUUU – UUUL – UUUU Step 1: Identify the sub-problem • Modify the definition of a dangerous stack • Stack is dangerous if: – It contains 3 adjacent uranium boxes OR – It contains K adjacent uranium boxes at the bottom (K <= 3) Step 2: Form a Recursive Solution int doit(int height, int bottom) { if (bottom == 0) return 1 << height; if (height == 0) return 0; return doit(height - 1, 3) + doit(height - 1, bottom - 1); } Step 3: Recursion -> DP int doit(int height, int bottom) { if (bottom == 0) return 1 << height; if (height == 0) return 0; if (cache[height][bottom] >= 0) return cache[height][bottom]; return cache[height][bottom] = doit(height - 1, 3) + doit(height - 1, bottom - 1); } Headmaster’s Headache (UVA 10817) Headmaster’s Headache (UVA 10817) • S subjects, 1 <= S <= 8 • M teachers you have, each teaches some of the subjects, 1 <= M <= 20 • N applicants from whom you can hire, each teaches some of the subjects 1 <= N <= 100 • Each teacher and each applicant has a salary they require • What is the minimum budget the headmaster needs so that each subject is taught by at least 2 teachers? Headmaster’s Headache (UVA 10817) Name Anna Must Salary Hire? YES 55,000 Bob YES 50,000 Carl YES 60,000 Math? Phys? Chem? YES YES YES Donald 75,000 YES Emil 90,000 YES Fred 50,000 YES YES YES Questions to Think About • What are different possible representation of the sub-problem? What are the advantages and disadvantages of each? • Would you prefer to solve this problem using memoization or iterative DP? What are the advantages and disadvantages of each? Mailbox Manufacturer’s Problem (UVA 882) • You have 1 <= k <= 10 mailboxes • At most 100 crackers fit into a mailbox • If a mailbox can withstand x fire-crackers, it can also withstand x - 1 fire-crackers • After explosion, a mailbox is either totally destroyed or unharmed • How many fire-crackers do you need to guarantee you will find out the smallest number of crackers that blow up a mailbox?