Consider the following variation on the change-making problem: you are given den
ID: 3765061 • Letter: C
Question
Consider the following variation on the change-making problem: you are given denominations x1;x2...xn, and you want to make change for a value v, but you are allowed to use each denomination at most once. For instance, if the denominations are 1, 5, 10, 20, then you can make change for 16 = 1 + 15 and for 31 = 1 + 10 + 20 but not for 40 (because you can’t use 20 twice).
Input: Positive integers x1;x2...xn; another integer v.
Output: Can you make change for v, using each denomination xi at most once?
Show how to solve this problem in time O(nv).
Explanation / Answer
change_making( x 1 , ..., x n , V )
Input: You are given denominations x1;x2...xn, and you want to make change for a value v, but you are allowed to use each denomination at most once
Output: True if you make change for v, using each denomination xi at most once
false otherwise
Declare an array D of size V + 1
D[0] = true
for i = 1 to V
D[i] = false
for v = 1 to V :
for j = 1 to n :
if xj < v :
D[ v ] = D[ v ] V D[ v - x j ]
else:
D[ v ] = false
return D[ V ]
Algorithm Analysis -> here are two for loops in the algorithm where one loop runs | V | times while the other loops run | n | times. Therefore the complexity of the algorithm is O( nV )