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
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]))
max(pole, key = lambda x: x[1]) #usporiadaj podla druhej hodnoty
$5000*4700 = 4700*5000$, teda vyhodnejsie pouzit $5000$-vky.
Kolko 4700-viek sa uz da nahradit 5000-vkami?
from math import gcd
5000//gcd(4700, 5000)
x=7
for i in range(1,100):
if min_poc_plat_greedy(i*x) < i:
print(i)
break
Vieme vypocitat presne ohranicinie?
x=4700
for i in range(1,100):
if min_poc_plat_greedy(i*x) < i:
print(i)
break
Rychlejsie greedy - zobrat naraz tolko kolko sa da.
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)])
Predpocitanie pre cifry pri platbe 1,2,5, ...
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)])
print([min_poc_plat_greedy(i) for i in range(1000000)] == [min_poc_plat_cifry(i) for i in range(1000000)])
max([min_poc_plat_greedy(i) for i in range(1000000)])