import functools
import time
import sys
x=150000000
sys.setrecursionlimit(x)
def kovanci_rekurzija(tabela_kovancev,vsota):
    '''rekurzivna rešitev, ki vrne najmanjše število kovancev, ki jih potrebujemo, da dobimo podano vsoto '''
    if vsota == 0:
        return 0
    try:
        return 1 + min([kovanci_rekurzija(tabela_kovancev,vsota-kovanec) for kovanec in tabela_kovancev if vsota-kovanec >= 0])
    except:# takega števila ni mogoče dobiti z danim naborom kovancev
        return float('inf')

tabela_kovancev= [25, 10, 5]

def rekurzija_kovanci(tabela,vsota): #do cca 25000
    @functools.lru_cache(maxsize=None)
    def kovanci_rekurzija_v2(vsota):
        if vsota == 0:
            return 0
        try:
            return 1 + min([kovanci_rekurzija_v2(vsota-kovanec) for kovanec in tabela if vsota-kovanec >= 0])
        except:# takega števila ni mogoče dobiti z danim naborom kovancev
            return float('inf')
    return kovanci_rekurzija_v2(vsota)
    
    

        
tabela_kovancev= [25, 10, 5]
V = 30
a = kovanci_rekurzija(tabela_kovancev,V)
a = kovanci_rekurzija(tabela_kovancev,1)
tabela_kovancev= [1,5,6,9]
V = 13
b = kovanci_rekurzija(tabela_kovancev,V)

# for i in range(5,16):
#     print(kovanci_rekurzija(tabela_kovancev,i))
    
    
def kovanci_pozresna(tabela_kovancev,vsota):
    '''naivna metoda za iskanje najmanjšega število kovancev, ki jih potrebujemo, da dobimo podano vsoto '''
    #kovance uredimo po velikosti
    #     tabela_kovancev.sort()
    stevec = 0
    for kovanec in tabela_kovancev[::-1]:
        while vsota >= kovanec:
            vsota -= kovanec
            stevec +=1
        if vsota == 0:
            return stevec
    return float('inf')
        
# for i in range(5,16):
#     print(i,kovanci_pozresna(tabela_kovancev,i))     #protiprimer


def kovanci_dinamicna(tabela_kovancev,vsota):
    '''dinamična metoda za iskanje najmanjšega število kovancev,
       ki jih potrebujemo, da dobimo podano vsoto
    '''
    #ustvarimo tabelo
    tabela = [float('inf')]*(vsota +1)
    tabela[0] = 0
    for i in range(1,vsota+1):
        for kovanec in tabela_kovancev:
            if kovanec <= i:
                potrebujemo = 1 + tabela[i-kovanec]
                tabela[i] = min(potrebujemo,tabela[i])
    return tabela[-1]

tabela_kovancev = [1,2,5,10,20]
for i in [500,1000,2000,4000,8000]:
    print(i)
    cas1 = time.time()
    kovanci_dinamicna(tabela_kovancev,i)
    cas2 = time.time()
    print(cas2-cas1)
    
    cas1 = time.time()
    rekurzija_kovanci(tabela_kovancev,i)
    cas2 = time.time()
    print(cas2-cas1)