Counting money problem is an optimization problem in which the Change (coins, paper notes) is to be count out for a certain amount of money (N) in minimum possible number of coins/bills.
Like 0/1 Knapsack problem in the Dynamic Programing solution for Making change, we also build a table C [k, N]. Columns in this table denote the amount ‘j’ starting from zero and increasing sequentially up to money N for which Change is to be count. Rows ‘i’ in table C denote available denominations d[i] (value of coin/note) starting from lowest value coin in the system and increasing in steps (of next denominations) up to ‘d[k]’ which is the largest note less than amount N.
At the start, all the values c[i, 0] in column zero are filled and then cells c[1, j] of first row (for lowest coin value d) are fully filled. After that, rest of the rows are filled one by one, deciding among the ‘Using’ and ‘Not using’ of the coin/note of value d[i], for each cell. If value d[i] of coin/note ‘i’ is greater than corresponding ‘j’ value, then it is not taken in use and resultantly the optimum number for this cell (c[i, j]) is the value in c[i-1, j]. For other cells, decision (Using/Not using) is made by comparing the values of c[i-1, j] and (1+ c[i, j-d[i]]), filling c[i, j] with minimum of both the values. Finally the value in the last cell (c[k, N]) is the required optimum value of Change count for N.
Suppose you have to give Money-Change for the amount of Rs.18 with least possible number of coins/notes. Currently the denominations for Pakistan currency system in Rupees are coins of 1, 2, 5 and paper notes of 10, 20, 50, 100, 500, 1000, and 5000.
You are required to determine whether the Greedy-approach gives optimum value or not in this case by calculating the required number of total coins/bills through both the solution methods.
Part 1 – Using Dynamic Programming [10 marks]
Part 2 – Using Greedy algorithm [5 marks]
Important Note: You have to show all the values for dynamic programming solution in the rows and columns of a single table only. There is no need to make separate tables for intermediate steps.