Bankomat

V bankomate sú uložené bankovky. Dokáže vám vyplatiť presne požadovanú sumu?

Na vstupe máte n čísel a požadovanú sumu. Na výstup vypíšte Ano, ak je možné danú sumu vyplatiť presne; ináč Nie

bankovky = [int(_) for _ in input().split()] #nacita medzerou oddelene cisla
n = len(bankovky) #pocet bankoviek
print(n)
s = int(input())

1 2 5 7
4
10

Riešenie hrubou silou (skúšanie všetkých možností): Vyskúšame, aké sumy sa dajú vyplatiť - ak je medzi nimi hľadaná, tak vypíšeme "Ano"

Koľko je možností pre n bankoviek?

Každú možnosť môžeme reprezentovať zoznamom použitých bankoviek, alebo z opačného uhla pohľadu pre každú bankovku vieme, či je v danej možnosti použitá. Pre každú bankovku teda máme dve možnosti (0/1 = je/nie je použitá). Celkovo je teda 2^n možností.

2**n # 2 na n-tu

16

Jedno možné riešenie je lexikograficky generovať všetky postupnosti núl a jednotiek

postupnost = [0]*n #zacneme postupnostou nul
def generuj(uroven): #postupne generujeme postupnost zlava doprava; ideme generovat na pozicii uroven
    if uroven == n: #ak uz mame celu postupnost, treda vsetky jej prvky
        print(*postupnost) #vypise postupnost ako medzerou oddelene cisla (nie zatvorky a ciarky)
        return #koncime
    for hodnota in range(2):
        postupnost[uroven] = hodnota #skusime danu hodnotu na zadanej urovni
        generuj(uroven+1)
generuj(0) #na zaciatku mame prazdnu postupnost, nula prvkov

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Pre každú postupnosť núl a jendotiek spočítame súčet

postupnost = [0]*n #zacneme postupnostou nul
def generuj(uroven):
    if uroven == n: #ak uz mame celu postupnost, teda vsetky jej prvky
        suma = 0 #postupne spocitame
        for u in range(n):
            if postupnost[u] == 1:
                suma += bankovky[u]
        print(*postupnost, "=", suma) #doplnime vystup aj o sumu
        return #koncime
    for hodnota in range(2):
        postupnost[uroven] = hodnota #skusime danu hodnotu na zadanej urovni
        generuj(uroven+1)
generuj(0) #na zaciatku mame prazdnu postupnost, nula prvkov

0 0 0 0 = 0
0 0 0 1 = 7
0 0 1 0 = 5
0 0 1 1 = 12
0 1 0 0 = 2
0 1 0 1 = 9
0 1 1 0 = 7
0 1 1 1 = 14
1 0 0 0 = 1
1 0 0 1 = 8
1 0 1 0 = 6
1 0 1 1 = 13
1 1 0 0 = 3
1 1 0 1 = 10
1 1 1 0 = 8
1 1 1 1 = 15

Kratší, jednoriadkový, zápis pre sumu

suma = sum([bankovky[u] for u in range(n) if postupnost[u] == 1])
print(suma)

15

Doplníme o testovanie hľadanej sumy s

postupnost = [0]*n #zacneme postupnostou nul
def generuj(uroven):
    if uroven == n: #ak uz mame celu postupnost, treda vsetky jej prvky
        return s == sum([bankovky[u] for u in range(n) if postupnost[u] == 1])
    for hodnota in range(2):
        postupnost[uroven] = hodnota #skusime danu hodnotu na zadanej urovni
        if generuj(uroven+1):
            return True
    return False
print("Ano" if generuj(0) else "Nie") #vypise Ano, ak sa da; inac Nie

Ano

Iné riešenie je využiť zápis čísel v dvojkovej sústave - teda vygenerovať všetky čísla od nula po 2^N-1

from bitstring import BitArray
for i in range(2**n):
    print(BitArray(uint=i,length=n).bin) #vypise zapis cisla

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Efektívnejšie riešenie je použitím dynamického programovania, postupného pamätania si všetkých možných súčtov z prvých k bankoviek

  File "<ipython-input-8-5e981d013db0>", line 1
    Efektívnejšie riešenie je použitím dynamického programovania, postupného pamätania si všetkých možných súčtov z prvých k bankoviek
                         ^
SyntaxError: invalid syntax