4. Given an unlimited supply of coins of denominations 21,...,n (each are positive integers). We want...

 

Transcribed Image Text:

4. Given an unlimited supply of coins of denominations 21,...,n (each are positive integers). We want to make change for some value v (also a positive integer), so we want to find a set of coins whose values add up to equal v. For example, if x₁ = 5, x2 = 8, 23 = 13, and v = 31, then we can take one of 21 and two of 23 to make change for v. If v=14, then we are not able to make change. Give a O(nv) dynamic programming algorithm to 1. decide if this is possible for a given value v, and if so, 2. return the set of coins used to make change. 4. Given an unlimited supply of coins of denominations 21,...,n (each are positive integers). We want to make change for some value v (also a positive integer), so we want to find a set of coins whose values add up to equal v. For example, if x₁ = 5, x2 = 8, 23 = 13, and v = 31, then we can take one of 21 and two of 23 to make change for v. If v=14, then we are not able to make change. Give a O(nv) dynamic programming algorithm to 1. decide if this is possible for a given value v, and if so, 2. return the set of coins used to make change.

Answer rating: 100% (QA)

The problem you described is known as the Coin Change problem and it can be solved using a dynamic programming approach with a time complexity of Onv ... View the full answer