Predstavme si jednorozmernú hraciu plochu. Prvé (ľavé) políčko je štartovacie, posledné (pravé) cieľové. Ostatné políčka reprezentujú rôzne mestá a obahujú číselný údaj - mýto za prechod mestom. V jednom ťahu sa hráč pohybuje o 1 až tri políčka (hádže sa kockou, kde sú hodnoty 1, 2, 3 dva krát).
Akú minimálnu sumu je možné dosiahnuť pri uvedenej hre, presun zo štartovacieho do cieľového políčka?
Môžeme odsimulovať všetky možnosti rekurziou:
myto = [0, 5, 3, 4, 2, 3, 5, 0] #hodnota myta na danom policko
n = len(myto) #pocet policok
najmenej = sum(myto)
def opt(policko, cena): #vstupili sme na policko a uz sme zaplatili cenu
global najmenej, n
print(policko, cena) #na dane policko sa vieme dostat s cenou
cena += myto[policko]
if policko == n-1:
if cena < najmenej:
najmenej = cena
return
for i in range(policko+1, min(policko+4, n)): #skoc o 1-3 policka, ale nie mimo hraciu plochu
opt(i, cena)
opt(0, 0) #zaciname na policku 0, cena doteraz 0
print(najmenej)
myto = [0, 5, 3, 4, 2, 3, 5, 0] #hodnota myta na danom policko
n = len(myto) #pocet policok
def opt(policko): #vypocita optimalnu hodnotu pre
print(policko)
if policko == 0:
return myto[policko]
return myto[policko]+min([opt(x) for x in range(max(0,policko-3), policko)])
print(opt(n-1))
myto = [0, 5, 3, 4, 2, 3, 5, 0] #hodnota myta na danom policko
myto= [0,8,5,1,1,3,4,4,1,2,0] #greedy - skok na najmensie mozne myto na 3 polickach - nefunguje
n = len(myto) #pocet policok
opt = [0]*n #optimalne riesenie, najmensia cena ako sa dostat na policko i
#pocitame dynamickym programovani zlava do prava
for policko in range(1, n): #vsetky policka postupne zlava, do druheho
opt[policko] = myto[policko]+min([opt[x] for x in range(max(0,policko-3), policko)])
print(opt) #vsetky medzivysledky
print(opt[n-1]) #vysledok
bankovky = [int(_) for _ in input().split()] #nacita medzerou oddelene cisla
n = len(bankovky) #pocet bankoviek
sucet = sum(bankovky)
suma = [False]*(1+sucet) #da sa zaplatit hodnota i, maximalna je sucet vsetkych bankoviek
suma[0] = True #na zaciatku vieme vtplatit iba 0
print(suma)
print('-----')
for b in bankovky:
for s in range(sucet-b, -1, -1): #aktualizujeme od konca, od sucet-b az po 0
if suma[s]:
suma[s+b] = True #ak sme vedeli zaplatit cenu s, tak teraz vieme aj s+b
print(b, ':', suma)
print(suma[4]) #da sa vyplatit konkretna suma
nemusime stale pole od konca (sucet), ale staci od poslednej jednotky, teda priebezneho suctu
sucet = sum(bankovky)
suma = [False]*(1+sucet) #da sa zaplatit hodnota i, maximalna je sucet vsetkych bankoviek
suma[0] = True #na zaciatku vieme vtplatit iba 0
print(suma)
print('-----')
sucet = 0
for b in bankovky:
for s in range(sucet, -1, -1): #aktualizujeme od konca, od sucet-b az po 0
if suma[s]:
suma[s+b] = True #ak sme vedeli zaplatit cenu s, tak teraz vieme aj s+b
sucet += b
print(b, ':', suma)
print(suma[4]) #da sa vyplatit konkretna suma