Question

Dynamic programming

Make the table for making $12 by using the denominations $1, $4, and $10. Show the traceback for the optimal set of the money used.

Answer 1

This problem is part of a problem called Minimum Coins Needed, in this problem we are given a target number and a set of valid coins to use, and we need to find the minimum number of coins from these available coins such that their sum will give the target number, provided we can use these coins in any number.

So, before understanding traceback, we'll understand how to fill the table using dynamic programming.

So, the idea here is to find minimum coins for smaller targets for given coins and then solve for the given target.

eg, first we'll find the minimum number of coins needed to get the target of $0 to $12, given that coin available is of $1

then find the minimum coins needed to get a target of $0 to $12, given that coins available is $1 and $4

then minimum coins needed to get the target of $0 to $12, when coins available are all three i.e $1, $4, $10

	$0	$1	$2	$3	$4	$5	$6	$7	$8	$9	$10	$11	$12
$1
$4
$10

The column contains the target to achieve, and Row contains coins available, therefore, there is an array in which coins[0] = 1, coins[1] = 4, coins[2] = 10

Since we need 0 of any denomination to get a target of 0, therefore, the first column is all 0,

And since we need 1*target to get the minimum number of coins needed to achieve the target if only 1 rupee coin is available, therefore,

	$0	$1	$2	$3	$4	$5	$6	$7	$8	$9	$10	$11	$12
$1	0	1	2	3	4	5	6	7	8	9	10	11	12
$4	0
$10	0

Now, we know that we cannot fulfill the target if the target < coins available, for eg, we cannot achieve $3 using $4 coin, therefore, we have to use $1 coins instead for that, and also to note that a coin will only be used if the target is >= coin

So, to proceed with this, we need to fill the table with the minimum possible coins used from all available coins, and to achieve this the recurrence relation is:

if j >= coins[i]:   // if target at column j is greater than coin available
     
    // minimum of if only till previous coins is considered and till the current coin is considered

    dpTable[i][j] = minimum(dpTable[i-1][j], 1 + dpTable[i][j-coins[i]]

else:
   
    // if target at column j is less than coin available, then we cannot use the current coin
    // and we have to use minimum coins needed till previous coins considered.

    dpTable[i][j] = dpTable[i-1][j]

Therefore, the table after filling using the above relation is:

	$0	$1	$2	$3	$4	$5	$6	$7	$8	$9	$10	$11	$12
$1	0	1	2	3	4	5	6	7	8	9	10	11	12
$4	0	1	2	3	1	2	3	4	2	3	4	5	3
$10	0	1	2	3	1	2	3	4	2	3	1	2	3

And the answer is dpTable[ 2 ][ 12 ] = 3, i.e we need minimum three coins to get $12 from $1, $4, $10

Now, we'll want to know, what are those three coins i.e traceback:

We start the traceback from LastRow = 2, LastCol= 12 (i.e last filled index)

While LastCol != 0:

    if dpTable[ LastRow ][ LastCol]  == dpTable[ LastRow - 1][LastCol] :
          LastRow = LastRow - 1  
   
    else:
          Money_used.insert(coins[LastRow])
          LastCol = LastCol - coins[LastRow]

So, with above algorithm, we start from lastRow = 2 and LastCol = 12

And we can observe that

dpTable[2][12] == dpTable[1][12] == 3, therefore, decrement LastRow by 1 therfore LastRow = 1

Now LastRow = 1, LastCol = 12

dpTable[1][12] is not equal to dpTable[0][12], therefore, insert the coin at LastRow, i.e 4 into money used and decrement the LastCol by 4(coins[LastRow]) = 8

Now LastRow = 1, LastCol = 8

dpTable[1][8] is not equal to dpTable[0][8], therefore, insert the coin at LastRow, i.e 4 into money used and decrement the LastCol by 4(coins[LastRow]) = 4

Now, LastRow = 1, LastCol = 4

dpTable[1][4] is not equal to dpTable[0][4], therefore, insert the coin at LastRow, i.e 4 into money used and decrement the LastCol by 4(coins[LastRow]) = 0

Now, LastRow = 1, LastCol = 0, loop break, program over.

Money_used contains = 4, 4, 4