(Advanced) (20 pints) Dynamic programming. In the COIN land, there\'re k types o
ID: 3819206 • Letter: #
Question
(Advanced) (20 pints) Dynamic programming. In the COIN land, there're k types of coins (like quarter, dime, etc.) where each coin Ci has value v (say USD) Sorry, there're no bills All values are integers, and 1 v1 v2 v3 vk. You want to use as few coins as possible to pay exactly B (USD). Give a dynamic programming for this task. You just need to compute the minimum number of coins needed to pay B Any running time polynomial in B and k is acceptable, but for full points, your running time must be O(kB). Explain your running time.Explanation / Answer
Following is the required DP algorithm to find minimum number of coins to pay B :
If B == 0 : then answer is 0
else : minimumCoinsRequired( B , Coins ) =
min { 1 + minimumCoinsRequired( B - vi , Coins ) } over all coins, such that vi <= B
Note that how solution for some value V depends on solution for values V', where V' < V. Thus we need to calculate previous values first.
So, we start finding values for B=1, B=2....till given value B. And, for each time, we have to iterate over all coins ( i.e. k times , as shown in else loop of pseudo code above ). Thus in total, we have to iterate in total k*B times which gives us running time as O(kB)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.