SICP counting change problem—why does N = X + Y?

2
votes

I'm a lurking layman trying to teach myself CS and am working my way through the first chapter of SICP at the moment.

I've come across the "counting change" example procedure and, like some others, although I understand the procedure itself, I'm struggling with the premise on which it is based:

Suppose we think of the types of coins available as arranged in some order. Then the following relation holds:

The number of ways to change amount a using n kinds of coins equals

  • the number of ways to change amount a using all but the first kind of coin, plus

  • the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.

To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.

The problem and procedure are available in context here, but I won't include the procedure as it's the logic above which I'm struggling with and not the procedure itself.

What I fail to understand is why these are always equal:

  1. The total number of "ways", less the "ways" to make the full amount without using the first type of coin.
  2. The number of "ways" using all types of coins to make the remainder of the amount, after subtracting the denomination of the first coin.

I've run through countless test examples manually, and yes, the relationship holds true, but I don't understand why.

The first sentence of their explanation makes sense:

observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do.

If we have the total number of "ways", we can divide that total into two groups according to that rule. No problem.

The second sentence is also clear:

Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin.

This simply states that the total number of ways is the sum of the ways that have been divided into two categories. OK.

This is where they lose me:

the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.

I assume this means that the "latter number" refers to all the ways to make change that must use at least one coin from the first denomination.

Why and how does this number equal the number of ways to make change with all coins for the total amount less the denomination of the first coin?

To try and visualise the problem, I restated it as trying to achieve a particular weight of 80Kg on a barbell with a set of 3 weight denominations:

  1. Red: 5Kg
  2. Green: 10Kg
  3. Blue: 20Kg

I layed each scenario out visually and indeed the relationship holds, but I still don't understand why:

Recursion for Bodybuilders

It feels as though the answer to this is right under my nose, but perhaps the sheer size of that particular appendage will eternally obscure the answer.

3
schemecomputer-sciencesicp
have you seen this answer on the question that you link to in your post? (feedback there seems to indicate it helped clear things up for quite some number of readers.) – Will Ness
you need to find ways(denomsList, targetSum), using zero or more coins from each denomination. either you use the first denomination coin, ways( denomsList, targetSum - first(denomsList)); or you never do: ways( rest(denomsList), targetSum). and of course, if A == append(B,C) then length(A) == length(B) + length(C). – Will Ness
another way to look at this is from the other end of the time arrow. :) imagine someone have already done all that for you and have put in front of you piles and piles of the bills, each pile summing up to the target sum. without loss of generality, let each pile be sorted so that bigger bills are on top. Divide all the piles into two groups: one with the biggest denomination bill on top each pile, and the other - without it. if the total number of piles is ways(denomsList, targetSum), then clearly the number of piles in the second group is ways( rest(denomsList), targetSum), (contd.) – Will Ness
and we can get the top bill off each pile in the first group, and the number of piles in it clearly won't be changed by that. having removed the top bill in each pile, we see that they all sum up to targetSum - first(denomsList) hence their number is ways(denomsList, targetSum - first(denomsList)) in total. and you're welcome. :) – Will Ness
I've come up with this new explanation thanks to your question, so thank you! I think it is clearer and more rigorous than the previous one. I'm going to add it into my answer, so thanks again. :) – Will Ness

3 Answers

2
votes

Let's imagine a simplified currency, with only ¤1 and ¤5 denominations. I ask you to produce ¤15, with the stipulation that at least one of the coins you give me must be a ¤5. How many ways could you do this? At this point, you could try generating all the ways to produce change for ¤15, and then throw out all those that do not meet my requirement. But it's simple to observe that you may as well start by setting aside a single ¤5 to meet my demand, and then work out how to make change for the remaining ¤10, in any way you choose.

1
votes

The trick here is that, given a bunch of denominations of coins one of which we'll call d, there are two ways of making change for some amount A:

  • don't use any coins of denomination d at all;
  • use at least one d (where I mean 'coin of denomination d' by 'd').

And the total number of ways of making change is the sum of these two ways (in particular there are no other ways we've missed).

So, in the first case we can compute the number of ways of making change using all the denominations but d (which we're obviously going to do by picking some other denomination & recursively using the trick we're about to use).

In the second case then we are going to use at least one d. So we know that, since we're using at least one d, the amount A can be split as A = d + (A - d): that's what it means to 'use at least one d'. So now how many ways of making a combination of coins like that are there? Well, the answer is that it's the number of ways of making change for an amount (A - d), except this time we're still allowed to use ds to make the change.

0
votes

Having thought this through over a few days with the help of other responders, I think this problem can be clarified (for me, at least) by adding an elaboration to the book's original explanation, after the line which reads:

But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.

I would phrase the new paragraph as follows:

This is because we can assume that for each combination that must contain at least one of the first kind of coin we have already used ("handed over") an instance of that amount. We simply need to calculate the ways to make change for the remainder of the amount n.

Therefore, there is no difference in the number of ways to make change for:

  1. the full amount using at least one of the first denomination, and
  2. the amount n less the value of the first denomination using any number of coins.

I subsequently managed to write my "weight room" version of the problem successfully, and its output matches my visual solution:

(define (loadways weight plates)
(cond
   [(= weight 0) 1]
   [(or (= (length plates) 0) 
        (< weight 0)
        ) 0]
   [else (+ (loadways weight (cdr plates))
            (loadways (- weight (car plates)) plates))]
   ))  

(define weight-rack (list 20 10 5))

(loadways 40 weight-rack)