Dynamic Programming (to make exact change using exact number of coins)

Question

I have unlimited 4 types of coins in cent: [1, 5, 25, 50]. How to pick EXACT 48 coins to make a exact 1 dollar change?(in any one valid way)

I know how to solve this recursively, but is it possible to solve it using DP? How? Thanks!

Answer 1

The possible solution may be the following (Haskell):

change d coins | null coins = []
               | d==0 = []
               | d>=coin = coin:change (d-coin) coins           
               | otherwise = change d (tail coins) where
        coin = head coins

Note that:

1. Given solution assumes that list of coins is desc sorted
2. Case when given value cannot be changed is not handled - I just did not include checks, just demonstrate the idea
3. Input value to change is in cents

Here are some results:

*Main> change 100 [50, 25, 5, 1]
[50,50]
*Main> change 99 [50, 25, 5, 1]
[50,25,5,5,5,5,1,1,1,1]
*Main> change 75 [50, 25, 5, 1]
[50,25]

If you have limitation on number of coins used in solution:

exactChange d coins n
    | d==0 && n==0 = [[]]
    | d>0 && n==0 = []
    | d==0 && n>0 = []
    | null coins = []
    | d>=coin = useFirstCoinSolutions ++ skipFirstCoinSolutions
    | otherwise = skipFirstCoinSolutions where
    coin = head coins
    rest = tail coins
    useFirstCoinSolutions = map (\x->coin:x) $ exactChange (d-coin) coins (n-1)
    skipFirstCoinSolutions = exactChange d rest n

This gives the following result:

*Main> exactChange 100 [50, 25, 5, 1] 48
[[25,25,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[25,5,5,5,5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,5,5,5,5,5,5,5,5,5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

So, it gives all possible solutions for change 100 cent with exact 48 coins

Explanation

1. First condition d==0 && n==0 defines that single solution found: we have zero amount to change and zero coins left to include in change;
2. Next three conditions defines that solution can not be found;
3. d>=coin this means that given amount is higher than first coin in set of coins so here we have to options: to proceed solutions search with first coin or to proceed without first coin of the set
4. For the case when first coin is higher than amount we can only proceed without using first coin