Coin Changing (Unlimited Coin Supply)

Example: coins = {3,1,2} and target = 8

Find out the minimum coin needed table for this data set.

---

Steps:

• Sort coins in ascending order: coins[] = {1,2,3}

• Make a table like this

  0	1	2	3	4	5	6	7	8
  0	inf	inf	inf	inf	inf	inf	inf	inf

• Iterate money from 1 to 8 and try to update the number of coins needed for making a particular money target

  formula:

  if current money is less then current taken coin then break this and go for next money iteration

  else if current money making coins is less then coins for (current money - taken coin) + 1 then upgrade current money making coins number with coins for (current money - taken coin) + 1

    for(int money=0; money<=target; money++)
    {
        for(int i=0; i<len; i++)
        {
            /// next coin from supply is greater then current coin in table
            if(money < coins[i])
                break;
            /// set minimum value for current coin amount making in table
            if(coin_table[money] > coin_table[money-coins[i]]+1)
                coin_table[money] = coin_table[money-coins[i]]+1;
        }
    }

---

Itrations:

Target : 1

coins = {1, 2, 3}

current table:

0	1	2	3	4	5	6	7	8
0	inf	inf	inf	inf	inf	inf	inf	inf

1 - coins[0] = 1 - 1 = 0
table[0] = 0

table[1] = inf
table[0] + 1 = 1 (minimum)

update the table:

0	1	2	3	4	5	6	7	8
0	1	inf	inf	inf	inf	inf	inf	inf

1 - coins[1] = 1 - 2 < 0

break this iteration and go for next target

---

Target : 2

coins = {1, 2, 3}

current table

0	1	2	3	4	5	6	7	8
0	1	inf	inf	inf	inf	inf	inf	inf

2 - coins[0] = 2 - 1 = 1
table[1] = 1

table[2] = inf
table[1] + 1 = 2 (minimum)

update the table

0	1	2	3	4	5	6	7	8
0	1	2	inf	inf	inf	inf	inf	inf

2 - coins[1] = 2 - 2 = 0
table[0] = 0

table[2] = 2
table[0] + 1 = 1 (minimum)

update the table

0	1	2	3	4	5	6	7	8
0	1	1	inf	inf	inf	inf	inf	inf

2 - coins[2] = 2 - 3 < 0

break this iteration and go for next target

---

How the table is building:

current table

0	1	2	3	4	5	6	7	8
0	1	1	inf	inf	inf	inf	inf	inf

How the table is upgrading

target >	0	1	2	3	4	5	6	7	8
coins/options	0	1	1	inf	inf	inf	inf	inf	inf
change for coins[0]	-	1	2	2	2	3	3	3	4
change for coins[1]	-	-	1	2	2	2	3	3	3
change for coins[2]	-	-	-	1	2	2	2	3	3
final look	0	1	1	1	2	2	2	3	3

---

Program Code