[Dynamic Programming] Making change using the fewest coins – recursive and iterative solutions.

http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html

 

class Coins:
    def __init__(self, coinValueList):
        self.coinValueList=coinValueList
        self.minCoins=[]
        self.coinsUsed=[]

    def _recMkChange(self,change):
        minCoins = change+1
        if change in self.coinValueList:
            self.minCoins[change] = 1
            self.coinsUsed[change] = change
            return 1
        elif self.minCoins[change] > 0:
            return self.minCoins[change]
        else:
            for i in [ c for c in self.coinValueList if c <= change ]:
                numCoins = 1 + self._recMkChange(change-i)
                if numCoins < minCoins:
                    minCoins = numCoins
                    self.minCoins[change] = minCoins
                    self.coinsUsed[change] = i
        return minCoins

    def recMkChange(self,change):
        if change < 1: return (0,[])
        self.minCoins=[0]*(change+1)
        self.coinsUsed=[0]*(change+1)
        return (self._recMkChange(change), self._showChange(change))

    def _dpMakeChange(self,change):
        for cents in range(change+1):
            coinCount = cents
            newCoin = 1
            for j in [ c for c in self.coinValueList if c &amp;lt;= cents ]:
                if self.minCoins[cents-j] + 1 &amp;lt; coinCount:
                    coinCount = self.minCoins[cents-j]+1
                    newCoin = j
            self.minCoins[cents] = coinCount
            self.coinsUsed[cents] = newCoin
        return self.minCoins[change]

    def dpMakeChange(self,change):
        if change < 1: return (0,[])
        self.minCoins=[0]*(change+1)
        self.coinsUsed=[0]*(change+1)
        return (self._dpMakeChange(change), self._showChange(change))

    def _showChange(self,change):
        coin = change
        result = []
        while coin &amp;gt; 0:
            thisCoin = self.coinsUsed[coin]
            if thisCoin == 0: 
                break # infinite loop safeguard
            result.append(thisCoin)
            coin = coin - thisCoin
        return result

c = Coins([1,5,10,25])
print c.recMkChange(63)

print c.dpMakeChange(63)

 

Leave a Reply

Your email address will not be published. Required fields are marked *