Mestá - hra s pohybom o 1-3 políčka

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:

In [19]:
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)
0 0
1 0
2 5
3 8
4 12
5 14
6 17
7 22
7 17
6 14
7 19
7 14
5 12
6 15
7 20
7 15
6 12
7 17
4 8
5 10
6 13
7 18
7 13
6 10
7 15
7 10
5 8
6 11
7 16
7 11
3 5
4 9
5 11
6 14
7 19
7 14
6 11
7 16
7 11
5 9
6 12
7 17
7 12
6 9
7 14
4 5
5 7
6 10
7 15
7 10
6 7
7 12
7 7
2 0
3 3
4 7
5 9
6 12
7 17
7 12
6 9
7 14
7 9
5 7
6 10
7 15
7 10
6 7
7 12
4 3
5 5
6 8
7 13
7 8
6 5
7 10
7 5
5 3
6 6
7 11
7 6
3 0
4 4
5 6
6 9
7 14
7 9
6 6
7 11
7 6
5 4
6 7
7 12
7 7
6 4
7 9
5
In [20]:
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))
7
4
1
0
2
0
1
0
3
0
1
0
2
0
1
0
5
2
0
1
0
3
0
1
0
2
0
1
0
4
1
0
2
0
1
0
3
0
1
0
2
0
1
0
6
3
0
1
0
2
0
1
0
4
1
0
2
0
1
0
3
0
1
0
2
0
1
0
5
2
0
1
0
3
0
1
0
2
0
1
0
4
1
0
2
0
1
0
3
0
1
0
2
0
1
0
5
In [28]:
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
[0, 8, 5, 1, 2, 4, 5, 6, 5, 7, 5]
5
In [29]:
bankovky = [int(_) for _ in input().split()] #nacita medzerou oddelene cisla
n = len(bankovky) #pocet bankoviek
1 2 5 7
In [45]:
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
[True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False]
-----
1 : [True, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False]
2 : [True, True, True, True, False, False, False, False, False, False, False, False, False, False, False, False]
5 : [True, True, True, True, False, True, True, True, True, False, False, False, False, False, False, False]
7 : [True, True, True, True, False, True, True, True, True, True, True, False, True, True, True, True]
False

nemusime stale pole od konca (sucet), ale staci od poslednej jednotky, teda priebezneho suctu

In [46]:
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
[True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False]
-----
1 : [True, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False]
2 : [True, True, True, True, False, False, False, False, False, False, False, False, False, False, False, False]
5 : [True, True, True, True, False, True, True, True, True, False, False, False, False, False, False, False]
7 : [True, True, True, True, False, True, True, True, True, True, True, False, True, True, True, True]
False
In [ ]: