CODEWITHSUNDEEP
algorithmrecursiondynamic-programmingcoin-change
qweszxcj
qweszxcj

Reputation: 153

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

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!

Upvotes: 1

Views: 1503

Answers (2)

Nyavro
Nyavro

Reputation: 8866

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

Upvotes: 1

naqushab
naqushab

Reputation: 804

Let we want to make n cents and we are given an infinite supply of each S = { S1, S2, S3, .. Sm } coins.

Dynamic Programming approach:

To count total number of solutions we can divide all set solutions into two sets

  1. Solutions that do not contain mth coin (or Sm).
  2. Solutions that contain at least one Sm.

Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Thus formulated as

count(n,m) = count(n, m-1) + count(n- sm, m)

With the following base cases:

  1. count(n,m) =1, n=0, one solution -- we have no money, exactly one way to solve the problem - by choosing no coin change, or, more precisely, to choose coin change of 0

  2. count(n,m) =0, n<0, no solution -- negative sum of money

  3. count(n,m) =1, n>=1, m<=0, no solution -- we have money, but no change available

Upvotes: 1

Related Questions