A-I-2

In [33]:
platidla = [1,2,5,10,20,50,100,200,500,1000,2000,5000]

def min_poc_plat_greedy(suma):
    pocet = 0
    for bank in reversed(platidla): #zacneme najvyssou bankovkou
        while bank <= suma: #plat bankovkou, kym sa da
            suma -= bank
            pocet += 1
    return pocet

n = 1000
x = 7
print(min([(i+min_poc_plat_greedy(n-i*x), i) for i in range((1+1000)//7)])) #skusime vsetky pocty bankovky 7
(1, 0)
In [34]:
x=47; pole = []
for n in range(1, 100000):
    pole.append(min([(i+min_poc_plat_greedy(n-i*x), i, n) for i in range(100) if n >= i*x]))
In [35]:
max(pole, key = lambda x: x[1]) #usporiadaj podla druhej hodnoty
Out[35]:
(4, 4, 188)

$5000*4700 = 4700*5000$, teda vyhodnejsie pouzit $5000$-vky.

Kolko 4700-viek sa uz da nahradit 5000-vkami?

In [39]:
from math import gcd
5000//gcd(4700, 5000)
Out[39]:
50
In [41]:
x=7
for i in range(1,100):
    if min_poc_plat_greedy(i*x) < i:
        print(i)
        break
3

Vieme vypocitat presne ohranicinie?

In [43]:
x=4700
for i in range(1,100):
    if min_poc_plat_greedy(i*x) < i:
        print(i)
        break
30

Rychlejsie greedy - zobrat naraz tolko kolko sa da.

In [59]:
platidla = [1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000]

def min_poc_plat_greedy(suma):
    pocet = 0
    for bank in reversed(platidla): #zacneme najvyssou bankovkou
        pocet_bank = suma // bank #maximalny pocet bankoviek danej hodnoty
        suma -= bank*pocet_bank #zaplat nimi
        pocet += pocet_bank #aktualizuj pocet bankoviek
    return pocet

print([min_poc_plat_greedy(i) for i in range(100)])
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6]

Predpocitanie pre cifry pri platbe 1,2,5, ...

In [55]:
def min_poc_plat_cifry(n): 
    pc = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3] #minimalne pocty bankoviek pre cifry 0,1,2,...,9
    pocet = 0    
    if n > 99999: #pre hodnoty od 100.000 musime pouzit 50.000-ky
        pocet = n // 50000
        n -= 50000*pocet
    while n > 0: #efektivne pre cifry, pre ktore existuju platidla, t.j. do 99999
        pocet += pc[n % 10]
        n = n // 10
    return pocet

print([min_poc_plat_cifry(i) for i in range(100)])
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6]
In [61]:
print([min_poc_plat_greedy(i) for i in range(1000000)] == [min_poc_plat_cifry(i) for i in range(1000000)])
Out[61]:
True
In [62]:
max([min_poc_plat_greedy(i) for i in range(1000000)])
Out[62]:
33