luke77

December 8th, 2008, 07:33 PM

Hi guys,

I'm trying to solve problems recursively and it is very frustrating. My goal is to develop a program that, given a set of coin values (like 100,25,10,5,1) and an amount of money, outputs all possible change combinations that can be used to make change. Not the number of possible combinations, but the actual combinations themselves.

So anyways, it seems like this problem lends itself to recursive processes, so I need to develop a base case and then a set of methods to reduce larger cases to this base case. I'm having trouble with this design, because I am not used to thinking in recursion.

The function should look something like:

makeChange(amount,coins):

coinVal = coins[0]

otherCoins=coins[1:]

if amount<coinVal:

return makeChange(amount,otherCoins)

if amount = coinval:

return [coinVal]

Then, as the "else" clause handling everything else, I could say:

else:

return ([coinVal] + makeChange((amount-coinVal),coins))

Now, this function would sort of begin to address the problem I really want to solve, but it only makes "optimal" change for a given value. I need to find every single combination. I could create a list of combinations, and then when a combination is generated test to see whether it is in the list, and if not change some parameter and call the function again, but this seems overly complicated and I'm not sure how I would implement it.

So, I'm stumped. I can express the solution in plain English: "If the amount of money is greater than or equal to the largest coin, subtract the amount of the largest coin from the total, then run the test using the adjusted total and the same set of coins. If the total is less than the largest coin, remove the largest coin and test with the adjusted list of coins." This is the problem that my current function solves (I think).

Then, in plain English, the rest of the solution: "For each coin in the solution set, generate all possible combinations of change that can make up this value". In other words, if my total is 30 cents, the "best" answer is (25,5). Then, we can reduce 25 to (10,10,5),(10,10,1,1,1,1,1),(10,5,5,5),etc....and for each of these new combinations of 25, we can also create the "5" in the original solution with either (5) or (1,1,1,1,1). Clearly for larger values it gets exponentially more complicated. But even this does not address all solutions, because what if we did not use a quarter in the original solution, and instead used (10,10,10)? Simply coming up with the optimal solution and then reducing it would not come up with this solution.

You get the point. I am sure I am overthinking this, but I am pretty frustrated. Can someone suggest how I should be thinking about this in simpler terms?

Also, to step back from this problem; in larger terms, how do you "think about" more complicated recursive problems like this? This problem is not that complex and I'm having trouble coming up with a plan to solve it. Clearly I need to have a different framework to address these problems.

Thanks for any advice.

I'm trying to solve problems recursively and it is very frustrating. My goal is to develop a program that, given a set of coin values (like 100,25,10,5,1) and an amount of money, outputs all possible change combinations that can be used to make change. Not the number of possible combinations, but the actual combinations themselves.

So anyways, it seems like this problem lends itself to recursive processes, so I need to develop a base case and then a set of methods to reduce larger cases to this base case. I'm having trouble with this design, because I am not used to thinking in recursion.

The function should look something like:

makeChange(amount,coins):

coinVal = coins[0]

otherCoins=coins[1:]

if amount<coinVal:

return makeChange(amount,otherCoins)

if amount = coinval:

return [coinVal]

Then, as the "else" clause handling everything else, I could say:

else:

return ([coinVal] + makeChange((amount-coinVal),coins))

Now, this function would sort of begin to address the problem I really want to solve, but it only makes "optimal" change for a given value. I need to find every single combination. I could create a list of combinations, and then when a combination is generated test to see whether it is in the list, and if not change some parameter and call the function again, but this seems overly complicated and I'm not sure how I would implement it.

So, I'm stumped. I can express the solution in plain English: "If the amount of money is greater than or equal to the largest coin, subtract the amount of the largest coin from the total, then run the test using the adjusted total and the same set of coins. If the total is less than the largest coin, remove the largest coin and test with the adjusted list of coins." This is the problem that my current function solves (I think).

Then, in plain English, the rest of the solution: "For each coin in the solution set, generate all possible combinations of change that can make up this value". In other words, if my total is 30 cents, the "best" answer is (25,5). Then, we can reduce 25 to (10,10,5),(10,10,1,1,1,1,1),(10,5,5,5),etc....and for each of these new combinations of 25, we can also create the "5" in the original solution with either (5) or (1,1,1,1,1). Clearly for larger values it gets exponentially more complicated. But even this does not address all solutions, because what if we did not use a quarter in the original solution, and instead used (10,10,10)? Simply coming up with the optimal solution and then reducing it would not come up with this solution.

You get the point. I am sure I am overthinking this, but I am pretty frustrated. Can someone suggest how I should be thinking about this in simpler terms?

Also, to step back from this problem; in larger terms, how do you "think about" more complicated recursive problems like this? This problem is not that complex and I'm having trouble coming up with a plan to solve it. Clearly I need to have a different framework to address these problems.

Thanks for any advice.