All about programming in GNU/LINUX

dynamic programming

Dynamic Programming : Making change for an given amount with least number of coins

Helloooooooooo !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Its been sometime since the last blog … loads of em are struggling to come out of the drafts ūüėõ I’ve been working on Dynamic programming concepts for a while now , So i thought of sharing my insights on the same by taking up the problem of finding ¬†change for the given amount using ¬†least possible no of currencies , and in the process i would love to explain what Dynamic programming is all about . Without wasting lot of time lets get into solving the problem .

Let me take an example scenario . Lets say you gotto make change for  11 cents and you have coins of 1,2,5  cents.  Now the question is what are various ways(the last step)  to reach to 11 cents considering you have coins of 1,2 and 5 cents ??? hmmm, thats not tough!

Add a 2 cents coin after having change for ¬† 9 cents ¬†(9 + 2 )= 11 cents | ¬†add 1 cents after having change for ¬†10 cents ( 10 +1)=11cents | ¬†add 5 cents after having change for ¬†6 cents (6 + 5)= 11 cents ¬†. Now we have 3 ways ( 9 + 2 , 10 + 1 , 6 + 5 ) But amongst these 3 approach which one would consist of minimal number of currencies or coins to make it to 11 ?? Hmm ….

Thats tricky !!!!! Well , that inturn depends on number of coins in the change for 9 , 10 and 6 cents. we have to consider the minimum amongst the 3 cases below

case 1: No.of.coins to make it to 9 cents (x) +  one  coin of 2 ceeents

case 2: No.of.coins to make it to 10 cents(y) + one coin of 1 cents (1)

case 3: No.of.coins to make it to 6 cents (z) + one coin of 5 cents (1)

In short we have to consider min(x+1 , y+1, z+1)

Now lets set  arbitrary values for x,y,z to be {3,2,2} respectively and Lets translate this logic into code for this particular value of amount for which we are supposed to find change using coins of 1,2,5 cents

Here is the code and explanation follows it , The names of variable used reflects their purpose . If you quickly want to execute and mess around with the code here is link https://ideone.com/M9qq4f . Here is the Github link of the code

amntForWhichChangeIsToBeFound = 11

coinsWeHaveUsingwhichChangeHastoBeFound = [1,2,5]

LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1)  

numberOfCoinsUsedForChange = [0]*(amntForWhichChangeIsToBeFound+1)

coinCount = 11
#In the worst the change will contain 11 coins with all of them ,obviously  lastCoinUsedForChange also  one being 1 cent
LastCoinUsedforChange = 1

numberOfCoinsUsedForChange[9] = 3
 
numberOfCoinsUsedForChange[10] = 2

numberOfCoinsUsedForChange[6] = 2 


for j in [c for c in coinsWeHaveUsingwhichChangeHastoBeFound if c<=amntForWhichChangeIsToBeFound]:
    #List comprehension in python , iterates only through values of array which satisfies if condition
    if numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound - j] + 1 < coinCount:
	    coinCount = numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound - j] + 1
	    LastCoinUsedforChange = j 
numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound] = coinCount 
LastcoinUsedToGetChangeArray[amntForWhichChangeIsToBeFound] = LastCoinUsedforChange 
print (numberOfCoinsUsedForChange)
print (LastcoinUsedToGetChangeArray)

In 5 and line 7 of the above code there is declaration and initialization to 0

LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1)  

numberOfCoinsUsedForChange = [0]*(amntForWhichChangeIsToBeFound+1)

The array element numberOfCoinsUsedForChange[i] contains the minimum number of coins used to obtain change for i cents . Thats is , numberOfCoinsUsedForChange[1] contains the minimum number of coins used to obtain change for 1 cent , numberOfCoinsUsedForChange[6] contains the minimum number of coins used to obtain change for 6 cent and it follows . But for now i have assigned arbitrary values to numberOfCoinsUsedForChange[6] , numberOfCoinsUsedForChange[9] , numberOfCoinsUsedForChange[10] , but in practical these values are to be computed .

Also the LastcoinUsedToGetChangeArray[i] contains the last coin used to get the change for i cents . LastcoinUsedToGetChangeArray[11] contains the last coin used in the change for 11 cents .

This sounds Ok , but You have now hard coded and assigned arbitrary values for inumberOfCoinsUsedForChange[6] , numberOfCoinsUsedForChange[9] , numberOfCoinsUsedForChange[10]  , but in real how do i have to compute in runtime ,how do i compute them ??

Yes , There are two ways to compute them . It can be recursively computed using top-down approach or iteratively computed using bottom-up approach . In the complete code sample later in the article ill be using the iterative approach .So using one of these approach the values are computed and the arrays are filled .
So now in this case to compute minimum number of coins required for change of 11 cents we need minimum number of coins required for change of 10,9 and 6 cents and those values are ¬†in turn are dependent on others(10 is dependent on 10 – [1,2,5],9 is dependent on 9 – [1,2,5] and so on …..) , so to solve this inter dependency ,one amongst either recursive or ¬†iterative approach can be used .

That sounds cool , but Size of both the arrays used is equal to the amount for which im finding change for , LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1) allocates and initializes array of size = (amntForWhichChangeIsToBeFound+1) , why are we wasting so much of memory ??

Yes , in the previous question above I spoke about the interdependencies , these arrays are used to store these interdependencies to avoid re-computation . These re-computations are avoided by storing these values and using them instead of recomputing them every-time . Yes , This needs more memory to be able to store these values , but this is traded off with the speed , This potentially can bring an exponentially time complexed algorithm down to polynomial and this is the core idea of Dynamic Programming . Yes the full program later First we’ll build the numberOfCoinsUsedForChange[] array from bottom-up approach . That is first we’ll compute ¬†numberOfCoinsUsedForChange[1] , numberOfCoinsUsedForChange[2], numberOfCoinsUsedForChange[3] and so on and these stored values are used to compute the later values because these serve as dependencies and recomputation is avoided .

Now analyze the output of the above program ,

In the output LastcoinUsedToGetChangeArray[11] contains value 1 , so 1 cent is the last coin used in the change . Now we know that the last coin is 1 cent , If we could find the last coin used in change for 10 cents (11 -1 )  this gives us one more coin in the minimum change for 11 cents , and this is stored in LastcoinUsedToGetChangeArray[10] , if this process is recursively followed all the coins used in getting the change can be obtained . Using this process PrintCoin function is written which prints out the coins used .

Phewwwwwwww!! Now i believe i spoke about enough of background work required to understand the logic easily , now lets scale it up to be able work with any value .

Here is the code which finds out the number of coins used and the coins used to find change for given amount with given set of coins . Again if you quickly want to execute and hack around here is the link of the code on cloud IDE https://ideone.com/eHhAcB. If you want to fork and mess around with the code here is the link of the code on Github Github link of the code

def printCoins(amntForWhichChangeIsToBeFound,LastcoinUsedToGetChangeArray):
    coin = amntForWhichChangeIsToBeFound
    while coin > 0:
        LastCoinForCoinCent = LastcoinUsedToGetChangeArray[coin]
        print(LastCoinForCoinCent)
        coin = coin - LastCoinForCoinCent

def main():
    amntForWhichChangeIsToBeFound = 68
    #edit it for the value you want it for 
    coinsWeHaveUsingwhichChangeHastoBeFound = [1,5,10,21,25]
    LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1)  
    numberOfCoinsUsedForChange = [0]*(amntForWhichChangeIsToBeFound+1)
    for cents in range(amntForWhichChangeIsToBeFound+1):
    	#This loop starts finding change from 1 cent, then 2,3,4..amntForWhichChangeIsToBeFound
        coinCount = cents
        LastCoinUsedforChange = 1
        for j in [c for c in coinsWeHaveUsingwhichChangeHastoBeFound if c <= cents]:
            if numberOfCoinsUsedForChange[cents - j] + 1 < coinCount:
    	        coinCount = numberOfCoinsUsedForChange[cents - j] + 1
    	        LastCoinUsedforChange = j 
        numberOfCoinsUsedForChange[cents] = coinCount 
        LastcoinUsedToGetChangeArray[cents] = LastCoinUsedforChange 
    #print (numberOfCoinsUsedForChange)
    #print (LastcoinUsedToGetChangeArray)	
    print("Number of coins used: "+ str(numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound]))
    print("Here are the coins used ")
    printCoins(amntForWhichChangeIsToBeFound, LastcoinUsedToGetChangeArray)

main()

Finallllllllly!! I’ll following up with few more posts on Dynamic programming and Golang implementation of HTTP/2 in the further posts to come …. Till then , Happy Coding ūüėÄ

Advertisements