Changing the bill with minimum number of coins

coinchanger.py

"""Changing the bill with minimum number of coins."""

class EmptyVError(Exception): pass

class CoinChanger:
    def __init__(self, C, v):
        if not v: raise EmptyVError

        self.C = C
        self.v = v
        self.n = len(v)

        # contains the minimum num of coin to change
        self.tab = [-1 for i in xrange(self.C + 1)]
        self.tab[0] = 0
        self.tab[1] = 1

        # contains the coin's value
        self.has = [-1 for i in xrange(self.C + 1)]
        self.has[1] = self.v[0]

    def M(self, c):
        assert c >= 0
        if self.tab[c] != -1: return self.tab[c]
        mindex = min((i for i in range(self.n) if c > self.v[i]),
                     key = lambda i : self.M(c-self.v[i]) + 1)
        self.tab[c] = self.M(c-self.v[mindex]) + 1
        self.has[c] = self.v[mindex]
        return self.tab[c]

    def solve(self):
        min_num = self.M(self.C)
        traceback = [] # has the values of coins
        rest = self.C
        while rest > 0:
            traceback.append(self.has[rest])
            rest -= traceback[-1]
        return (min_num, traceback)

import pytest
class TestCoinChanger:
    def test_empty(self):
        with pytest.raises(EmptyVError):
            CoinChanger(1,[]).solve()

    def test_simple(self):
        assert CoinChanger(3,[1]).solve() == ( 3, [1,1,1] )

    def test_1(self):
        solution = CoinChanger(5, [1,2]).solve()
        assert solution[0] == 3
        assert sorted(solution[1]) == [1,2,2]

    def test_2(self):
        # import rpdb2; rpdb2.start_embedded_debugger("1")
        solution = CoinChanger(34, [1,5,10]).solve()
        assert solution[0] == 7
        assert sorted(solution[1]) == sorted([10,10,10,1,1,1,1])