SICP: Structure and Interpretation of Computer Programs (24)

12 Name: #!/usr/bin/anonymous : 2008-05-06 19:23 ID:9Pp+L21/

Let's go to the counting change problem in Section 1.2.2

Question: How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

I realized that this problem is the same as this:

Given A >= 0 and d_k > 0, k being integers 1 to n.
Find x_k such that
x_1*d_k + x_2*d_2 + ... + x_n*d_n = A
where x_k are non-negative integers.

A is supposed to be the total amount of money. d_k are the denominations and x_k are the number of coins and n is the number of denominations.

I am pretty sure this is an exponential problem. Something like A^n/prod(d_k). What do you think?

Return Entire thread Last 50 posts
This thread has been closed. You cannot post in this thread any longer.