COEN 179 Lecture Notes - Lecture 20: Dynamic Programming, Horse Length, Longest Common Subsequence Problem

• School: Santa Clara University
• Department: Computer Engineering
• Course: COEN 179
• Professor: Tran

Document Summary

Input: change amount n, set of denominations d[0k-1] A[0k-1], where a[i] = # of available coins in denominations d[i] Output: smallest multisets of coins in given denominations whose total sum is n, such that s contains at most a[i] coins in denominations d[i] E. g. n = 14, d = {1, 5, 7, 10}, a = {3, 1, 1, 1} Optimal solution: 7 + 5 + 1 + 1. Dynamic programming: 1) start by allowing no denominations this restriction has easy solutions: no solutions exist for n > 0. 2)slowly add back denominations: 1, then 1, 5, then 1, 5, 7, then 1, 5, 7, 10 n = 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4. 0 1 2 3 _ 1 2 1+0 1+1 1+2 1+3 _ 1+1 1+2 1+3. D{1 , 5 , 7 , 10 } 0 1 2 3 _ 1 2 1 2 3 1 2 2 3 4.