Rešitev

Obvezni del

Napiši funkcijo cete(niz), ki prejme nek niz, ki vsebuje zgolj števke. Funkcija vrne seznam nizov, ki predstavljajo "čete" znotraj podanega niza, to je, podzaporedja naraščajočih števk.

Klic cete("2189684") vrne ["2", "189", "68", "4"].

Rešitev

Najprej sestavimo prazen seznam, v katerega bomo dajali čete in ga na koncu vrnili.

Nato gremo prek vseh znakov niza. Kdaj je potrebno začeti novo četo? No, kadar še nobene ni, torej na začetku niza (not cete), ali pa če je zadnji znak zadnje čete večji od novega znaka (cete[-1][-1] >= znak). Kadar je res kaj od tega, v seznam čet začnemo novo četo tako, da vanj preprosto pripnemo nov element, ki vsebuje ta znak.

Če ni tako in ne ustvarjamo nove čete, temveč dodajamo ta znak v zadnjo četo, pa ga pač dodamo.

def cete(niz):
    cete = []
    for znak in niz:
        if not cete or cete[-1][-1] >= znak:
            cete.append(znak)
        else:
            cete[-1] += znak
    return cete

Neobvezna dodatna naloga

Napiši funkcijo pakiraj(teze, maks_teza), ki prejme seznam tež stvari, ki bi jih radi zapakirali, in maksimalno težo paketa. Funkcija vrne seznam seznamov s težami, kot je razloženo v spodnjem primeru.

Recimo, da pokličemo pakiraj([2, 5, 2, 7, 5, 3, 2, 3, 5], 10). V prvi paket gredo stvari s težami [2, 5, 2], če bi dodali še naslednjo stvar, ki ima težo 7, pa bi s tem presegli podano maksimalno težo (10). V naslednji paket gre samo [7]; če bi dodali še 5, bi bilo to pretežko. V naslednji paket gredo [5, 3, 2], v zadnjega pa [3, 5].

Funkcija vedno jemlje stvari v takšnem vrstnem redu, v kakršnem so naštete v seznamu.

Klic pakiraj([2, 5, 2, 7, 5, 3, 2, 3, 5], 10) torej vrne [[2, 5, 2], [7], [5, 3, 2], [3, 5]].

Rešitev

Tole je popolnoma enako, le da imamo namesto nizov številke, pa pogoje je nekoliko drugačen.

def pakiraj(teze, maks_teza):
    paketi = []
    for teza in teze:
        if not paketi or sum(paketi[-1]) + teza > maks_teza:
            paketi.append([teza])
        else:
            paketi[-1].append(teza)
    return paketi

Še bolj neobvezna naloga, za razmišljanje

Če bi morali spakirati [5, 1, 7, 4, 3] in je največja dovoljena teža spet 10, bi funkcija vrnila [[5, 1], [7], [4, 3]], čeprav bi lahko sestavila [[5, 1, 4], [7, 3]].

Če bi morali spakirati [5, 4, 6, 3, 2], bi vrnila [[5, 4], [6, 3], [2]], čeprav bi šli [[5, 3, 2], [6, 4]].

Napiši funkcijo optimalni_paketi(teze, maks_teza), ki stvari ne jemlje vedno nujno po vrsti, temveč jih spakira v čim manj paketov.

Funkcija bo morda počasna. Ta, ki sem jo napisal jaz, za teste ne mojem računalniku potrebuje približno 10 sekund. Dalo bi se tudi boljše ... vendar to niso preproste stvari.

Rešitev

S funkcijo permutations iz modula itertools lahko sestavimo vse permutacije. Za vsako pokličemo pakiraj. Če je dobljeno pakiranje boljše od najboljšega doslej, si ga zapomnimo.

from itertools import permutations

def optimalni_paketi(teze, maks_teza):
    najboljsi = None
    for perm in permutations(teze):
        pakiranje = pakiraj(perm, maks_teza)
        if najboljsi is None or len(pakiranje) < len(najboljsi):
            najboljsi = pakiranje
    return najboljsi

To je seveda strašno počasno in še vedno počasnejše. Če imamo seznam s šestimi elementi in mu dodamo sedmega, bo permutacij sedemkrat več - in program sedemkrat počasnejši. Če dodamo še osmega, bo še osemkrat počasnejši. Če devetega, še devetkrat.

Žalostna resnica pa je, da za ta problem pravzaprav niti ni bistveno boljših rešitev. Stvari se olajšajo, če imamo kakšne omejitve, recimo to, da so vse teže cela števila. V splošnem pa so problemi te vrste navadno NP-polni. Kaj to pomeni, boste zares izvedeli v tretjem letniku. Doslej pa to pomeni, da so, v praksi, nerešljivi.