Unable to understand how the while loop extracts the least number of coins with given sum

Question

I was reading this classical Coin Problem (7.1): Given a set of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to form the sum n using as few coins as possible.

I fully understood the discussion until I encountered the last code snippet of the section Constructing A Solution:

    int first[N];  // N is sufficiently large

    value[0] = 0;
    for (int x = 1; x <= n; x++) {
       value[x] = INF;
       for (auto c : coins) {
         if (x-c >= 0 && value[x-c]+1 < value[x]) {
            value[x] = value[x-c]+1;
            first[x] = c;
         }
       }
    }

    while (n > 0) {
       cout << first[n] << "\n";
       n -= first[n]; 
    }

My doubt is pertaining to the way array first is storing the coin denominations and how the while loop at the last is able to extract the required coins.

For example consider this case when I have coins of denominations {1, 4, 5, 10, 20}, with each coin available as many numbers as needed. So to form a sum of 22, optimally I need one 20 unit and two 1 units. This is what the code gives as output, when properly coded.

But I am not able to undertand how this first array is storing the denomination values. So to understand this I printed out this first arrray and got this:

0 1 1 1 4 5 1 1 4 4 10 1 1 4 4 5 1 1 4 4 20 1 1

And I was more confused.

In short: please explain how first array stores values and how the while loop is able to print out only the required values.

Answer 1

Let us take a look at line 3 and 4 of the following part of the code.

1       for (auto c : coins) {
2         if (x-c >= 0 && value[x-c]+1 < value[x]) {
3            value[x] = value[x-c]+1;
4            first[x] = c;
5         }
6       }

value[x] should store the least number of coins needed to form x.
value[x-c] stores the least number of coins needed to form x-c.
Line 3 means, if we take coin c first and use value[x-c] coins to form the rest, x-c, we will use value[x-c]+1 coins to form c+(x-c)=x. So we can set value[x] to be value[x-c]+1.

Since first[x] is set to c at line 4, we can replace c by first[x].
Line 3 can be read again as, in order to use the least number of coins to form x, we can take coin first[x] first and then use the least number of coins to form the rest, x-first[x].

---

Let us read the while loop.

Initially, the target is n. Treating n as x above, we see that in order to use the least number of coins to form n, we can take coin first[n] first (so, we will print first[n] by cout << first[n] << "\n";) and then will use the least number of coins to form n-first[n].

Now the target is n-first[n]. This is the same situation as the initial situation. So we will set n to n-first[n], and repeat.

---

For example, when n=22.

Since first[22]=1, we will take coin 1 first.
The target to form next is 22-1=21.
Since first[21]=1, we will take coin 1 first. (In fact, this is the second coin.)
The target to form next is 21-1=20.
Since first[20]=20, we will take coin 20 first. (In fact, this is the third coin).
The target to form next is 20-20=0. No more action is needed to form 0.