Coin exchange method with value of power of 2 PYTHON [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

Once the machines take over, the denomination of every coin will be a power of two: 1-cent, 2-cent, 4-cent, 8-cent, 16-cent, etc. There will be no limit to how much a coin can be worth.

A set of coins makes change for n if the sum of the values of the coins is n. For example, the following sets make change for 7:

7 1-cent coins 5 1-cent, 1 2-cent coins 3 1-cent, 2 2-cent coins 3 1-cent, 1 4-cent coins 1 1-cent, 3 2-cent coins 1 1-cent, 1 2-cent, 1 4-cent coins Thus, there are 6 ways to make change for 7.

Write a function count_change that takes a positive integer n and returns the number of ways to make change for n using these coins of the future.

I have been working on this question for an hour trying to use tree recursion but it doesn't work. I was thinking about to use 2 branches of the current amount - 1 and the current amount - largest coin value possible but the outcomes are never satisfiable.

Please give me a suggestion of how to approach it...thx!

Answer 1

this is an example of dynamic programming

you can implement it with the standard formula for dynamic programming (see Coin Change Problem)

let s = {1,5,10,25} our coinset for now be standard coin denominations

let f(x,y) = number_of_ways_to_make_change let x=change_due;y=allowed_coinset_index

• notes: if y == 0 our allowed coinset is {1}, if y == 1 our allowed coinset is {1,5} ...
• any change_due has a trivial solution of 1 when our coinset consists only of {1} that is to say if you only have pennies there exists only one way to make change (all pennies)
• ergo f(anything,0) == 1 && f(0,anything) == 1 && f(anything,anthing < 0) == 0

let us solve for a few change_due values

change_due   function_call    
1             f(1,0) = 1
...
4             f(4,0) = 1
5             f(5,1) = f((5-5),1) + f(5,0) = 1 + 1 = 2
...
9             f(9,1) = f(9-5,1)+f(9,0) = f(4,1) + 1 = f(4,0*) + 1 = 1+1 = 2
10            f(10,2) = f(10-10,2) + f(10,1) = f(0,2) + (f(5,1)+f(10,0))= 1+(2+1) = 4

so we can see our base cases of

f(x,0) = f(0,y) = 1
f(x is less than zero,y) = f(x,y is less than zero) = 0

note that this applies for any set of coins

V this is the important part V

#if x,y are not in above conditions we want to recursively call ourselves allowing us to build up to a complex solution from several simpler solutions
f(x,y) = f(x-CHANGE_DENOM,y) + f(x,y-1)

lets keep playing with that table from above and see how many ways we can make 16 cents

S = [1,5,10,25] 
# our y is 2 (since S[2] = 10 which is the largest denomination < our change_due(16))
f(16,2) = f(16-S[2],2) + f(16,1) 
        = f(16-10,2) + f(16,1) = f(6,2) + f(16,1)
   f(6,2) = f(6-S[2]) + f(6,1) = 0 + f( 6,1) = 0+2#(see below) =
   f(16,1) = f(16-S[1],1) + f(16,0) = f(11,1) + 1
       f(11,1) = f(11-S[1],1) + f(11,0) = f(6,1) + 1
          f(6,1) = f(6-S[1],1) + f(6,0) = f(1,1) + 1
             f(1,1) = f(1-S[1],1) + f(1,0) = 0 + 1 = 1
          f(6,1) = f(1,1) + 1 = 1 + 1 = 2
       f(11,1) = f(6,1) + 1 = 2 + 1 = 3
   f(16,1) = f(11,1) + 1 = 3+1 = 4
f(16,2) = f(6,2) + f(16,1) = 2 + 4  = 6 ways to make change for 16 cents 

now you just need to make it work for your bigger coinset