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.