Gneče na trajektih so običajen pojav in Jadrolinija vlaga veliko naporov v to, da bi jih zmanjšala. Običajno na obali stoji kolona tovornjakov in potrebno je čim prej ugotoviti, kako velik trajekt potrebujemo, da jih lahko naenkrat prepeljemo.

Dano imamo torej zaporedje tovornjakov, ki bi jih radi razporedili na trajekt. Na trajektu bodo tovornjaki stali v treh pasovih in mi si lahko poljubno izberemo, na katerem pasu bo stal kateri tovornjak. Seveda pa skupna dolžina tovornjakov na nobenem od pasov ne sme presegati dolžine trajekta. Napiši program, ki bo za dano zaporedje dolžin tovornjakov poskusil ugotoviti, kako dolg je najkrajši trajekt, pri katerem bi se še dalo razporediti te tovornjake v tri pasove, ne da bi skupna dolžina tovornjakov na katerem od pasov presegla dolžino trajekta.

Vhodna datoteka: v prvi vrstici je celo število n (1 ≤ n ≤ 100), ki pove število tovornjakov. Sledi še n vrstic, v katerih so dolžine tovornjakov. Vsaka dolžina tovornjaka je celo število, večje ali enako 1 in manjše ali enako 100. Izhodna datoteka: V prvo vrstico izpiši dolžino najkrajšega trajekta, na katerega je tvojemu programu uspelo razporediti tovornjake iz vhodne datoteke v skladu z zahtevami naloge. (Testni primeri bodo zasnovani tako, da ta dolžina najkrajšega trajekta nikoli ne bo večja od 100.) Sledi naj še n vrstic, ki opišejo nek konkreten razpored tovornjakov na ta najkrajši trajekt: v i-ti izmed teh vrstic naj bo število 1, 2 ali 3, ki pove, na kateri pas je bil razporejen i-ti tovornjak iz vhodne datoteke. Točkovanje: če tvoja izhodna datoteka ne ustreza zgoraj opisanim zahtevam, dobiš pri tistem testnem primeru 0 točk, drugače pa je število točk odvisno od tega, kako dolg je tvoj trajekt v primerjavi z najkrajšim možnim. Recimo, da je pri nekem testnem primeru najkrajši možni trajekt dolg t* enot, v tvoji izhodni datoteki pa je trajekt dolžine t enot. Potem dobiš pri tem testnem primeru max{1, 10 − (t − t*)} točk. Z drugimi besedami, 10 točk dobiš le, če je tvoja rešitev najboljša možna (t = t*); sicer pa se ti odbije toliko točk, za kolikor je tvoj trajekt daljši od najkrajšega možnega, vendar največ devet točk (tako da zagotovo dobiš vsaj eno točko).

Primer vhodne datoteke:
7
26
15
29
30
30
16
10

Pripadajoča izhodna datoteka:
55
1
2
1
2
3
3
2

Na trajekt dolžine 55 lahko razporedimo tovornjake takole: 26 + 29 na en pas, 10 + 15 + 30 na drugega in 16 + 30 na tretjega. To je pri tem zaporedju tovornjakov tudi najkrajši možni trajekt.

Torej napisati moramo funkcijo, ki prebere vhodno datoteko, sestavi seznam z ustreznimi dolžinami tovornjakov in nato ugotovi kakšna razporeditev tovornjakov na pasove trajekta, bi bila najbolj ugodna, da bi potrebovali čim krajši trajekt. To najugodnejšo razporeditev po pasovih trajekta na koncu izpišemo na izhodno datoteko v zahtevani obliki.

Nalogo lahko rešimo tako, da sem napišemo dve funkciji in sicer: tovornjaki (vhodna, izhodna) in subsets (x). Prva nam s pomočjo druge funkcije pomaga do iskane rešitve problema.

Ideja rešitve je v tem, da najprej s funkcijo tovornjaki preberemo vhodno datoteko in števila, ki predstavljajo dolžino posameznega tovornjaka shranimo v nek seznam. Potem s pomočjo funkcije subsets poiščemo vse podsezname prej definiranega seznama. Z dobljenimi podseznami si pomagamo tovornjake razdeliti v tri pasove.

Paziti moramo, da vsakič v te tri pasove razdelimo natanko vse tovornjake in da se vsak lahko pojavi samo v enem pasu. Vsakič, ko razdelimo tovornjake v pasove, preverimo dolžino najdaljšega pasa. Če je ta dolžina krajša, od dolžine v prejšnjih razporeditvah, si zapomnimo trenutno razporeditev in dolžino trenutnega najdaljšega pasa. Ko preverimo vse možne različne razporeditve tovornjakov, imamo iskano minimalno potrebno dolžino trajekta in razporeditev tovornjakov po pasovih. Na koncu samo še izračunane vrednosti izpišemo na izhodno datoteko, v ustrezni obliki.

def subsets(x):
    assert type(x) == list, "Parameter x mora biti podan kot seznam."
    for i in range(len(x)):
        assert x[i] not in x[i+1:], "Seznam x mora vsebovati RAZLIČNE elemente."
        pass
    if x == []:
        return [[]]
    else:
        s = [x]
        for elem in x:
            tmp = x[:]
            tmp.remove(elem)
            new_sub = subsets(tmp)
            for y in new_sub:
                if y not in s:
                    s.append(y)
        return s

Funkcija subsets dobi kot parameter seznam , ki vsebuje same različne elemente. To je rekurzivna metoda. Vrne pa nam nov seznam, ki vsebuje vse "podmnožice - podsezname" prvotnega seznama (vrstni red elementov ni pomemben). Torej če je vhodni seznam vseboval n-elementov, potem vsebuje seznam, ki ga funkcija vrne natanko 2ⁿ-elementov.

import os

def tovornjaki (vhodna, izhodna):
    assert type(vhodna) == str and type(izhodna) == str, "Parametra morata biti podana kot niza."
    assert os.path.isfile(vhodna), "Vhodna datoteka ne obstaja."
    # Odpremo datoteko vhodna za branje.
    beri = open(vhodna, 'rt')
    # Ustvarimo datoteko izhodna za pisanje.
    piši = open(izhodna, 'wt')
    # Preberemo prvo vrstico vhodne datoteke in prebrano "število"(niz, ki ga pretvorimo v število), ki
    # predstavlja število tovornjakov shranimo v spremenljivko n.
    n = int(beri.readline())
    assert 1 <= n <= 100, "Prepeljemo lahko najmanj enega in  največ 100 tovornjakov."
    seznam = []
    # Prebrati moramo še toliko vrstic, kolikor je tovornjakov, torej toliko kolikor je n.
    for i in range(n):
        vrstica = beri.readline()
        # V seznam shranimo dvo-elementne podsezname. Prvo število v podseznamu predstavlja dolžino
        # tovornjaka, drugo število pa sem dodala, da bom lažje razlikovala tovornjake med sabo.
        assert 1 <= int(vrstica) <= 100, "Posamezen tovornjak je lahko dolg najmanj 1 in največ 100 enot."
        seznam.append([int(vrstica), i])
    # Preverimo, če imamo samo en tovornjak. Takrat je dolžina najkrajšega trajekta, ki ga potrebujemo,
    # enaka kar dolžini edinega tovornjaka.
    if len(seznam) == 1:
        piši.write(str(seznam[0][0]) + '\n' + '1')
        beri.close()
        piši.close()
        return
    # V tem primeru imamo vsaj dva tovornjaka!
    # S pomočjo funkcije subsets, v seznam podmnožice shranimo vse podmnožice seznama seznam.
    podmnožice = subsets(seznam)
    # Prva možnost, kako razporedimo tovornjake je tako, da vse damo v en pas. Takrat je minimalna potrebna
    # dolžina trajekta enaka kar vsoti vseh dolžin tovornjakov.
    minimum = sum(k[0] for k in seznam)

Funkcija tovornjaki najprej iz vhodne datoteke prebere število tovornjakov in njihovo dolžino. Dolžine tovornjakov shranimo v seznam. Če je v seznamu samo en tovornjak, potem je najkrajši potreben trajekt enak kar dolžini tega tovornjaka. Če pa je v seznamu več kot en tovornjak, na temu seznamu uporabimo funkcijo subsets , ki vrne seznam, katerega elementi so vse "podmnožice - podseznami" prvotnega seznama. Ta vrnjeni seznam shranimo v spremenljivko podmnožice . Definiramo še spremenljivko minimum , ki ima na začetko kar vrednost, ki je enaka vsoti dolžin vseh tovornjakov.

# Z for zanko gremo po seznamu podmnožice in sicer od konca proti začetko seznama.
    for j in range(n-1, -1, -1):
        # V seznam a shranimo vse j-elementne podmnožice monožice podmnožice.
        a = [b for b in podmnožice if len(b) == j]
        # V seznama d in f pa shranimo še toliko elementne podmnožice množice podmnožice, da bojo skupaj
        # seznami a, d in f natanko n-elementni.
        for c in range(n-j+1):
            d = [e for e in podmnožice if len(e) == c]
            f = [g for g in podmnožice if len(g) == n-j-c]
            # Gremo po elemetih (podseznamih) seznamov a, d in f. Če kombinacija podseznamov vsebuje same
            # različne tovornjake, sestavimo seznam nov, ki vsebuje vsak tovornjak natanko enkrat.
            for el1 in a:
                for el2 in d:
                    for el3 in f:
                        el11 = []
                        el22 = []
                        for tovornjak1 in el1:
                            if tovornjak1 not in el2 and tovornjak1 not in el3:
                                el11.append(tovornjak1)
                        for tovornjak2 in el2:
                            if tovornjak2 not in el3:
                                el22.append(tovornjak2)
                        if len(el1) == len(el11) and len(el2) == len(el22):
                            nov = [el1, el2, el3]
                            # Izračunamo dolžino posameznega potrebnega pasu.
                            EL1 = sum(znak1[0] for znak1 in el1)
                            EL2 = sum(znak2[0] for znak2 in el2)
                            EL3 = sum(znak3[0] for znak3 in el3)
                            # Če je najdaljša dolžina pasu manjša od prejšnjega minimuma, smo dobili novo
                            # razporeditev, ki je krajša od prejšnje.
                            if max(EL1, EL2, EL3) < minimum:
                                minimum = max(EL1, EL2, EL3)
                                najkrajši = nov
    # Ko se zanka konča, dobimo dolžino najkrajšega trajekta in ustrezno razporeditev tovornjakov.
    # Na izhodno datoteko zapišemo dolžino trajekta, ki ga potrebujemo in v katerem pasu bo posamezen tovornjak.
    piši.write(str(minimum)+'\n')
    for tovornjak in seznam:
        if tovornjak in najkrajši[0]:
            piši.write('1\n')
        elif tovornjak in najkrajši[1]:
            piši.write('2\n')
        else:
            piši.write('3\n')
    beri.close()
    piši.close()

Definiramo 3 sezname: a , d in f . Ti se spreminjajo, saj so zapisani v for zanki. Ti seznami vsebujejo elemente seznama podmnožice . Zgornja koda je dobro komentirana, zato si jo podrobno oglejte. Težko je natančno napisati kaj sploh koda naredi. Zato bom vse skupaj bolj poenostavila.

S pomočjo prej definiranih seznamov, sestavimo nov seznam, ki vsebuje 3 podsezname. Vsak iz med teh podseznamov predstavlja razporeditev tovornjakov v enem pasu trajekta. Poskrbeli smo, da so zajeti vsi tovornjaki, vendar se posamezen tovornjak pojavi natanko v enem podseznamu. Skozi zanko spremljamo najkrajšo možno dolžino trajekta in jo hranimo v spremenljivki minimum . Hranimo tudi seznam, v katerem je trenutno najugodnejša razporeditev tovornjakov.

Ko se zanka zaključi smo v bistvu že rešili problem. Sedaj samo še na izhodno datoteko izpišemo dolžino najkrajšega trajekta in pasove v katerih se posamezen tovornjak nahaja (vsako v svojo vrstico).

Pri funkciji subsets moramo preveriti naslednje:

• kaj se zgodi, če ji kot parameter podamo niz, decimalno število ali celo število.
• kaj se zgodi, če ji kot parameter podamo seznam, ki ne vsebuje samih različnih elementov.
• če so seznami, ki jih vrača funkcija ustreznih dolžin (če ima seznam ustrezno število "podmnožic - podseznamov").

Pri funkciji tovornjaki moramo preveriti naslednje:

• kaj se zgodi, če ji kot parameter podamo sezname, decimalna števila ali cela števila.
• kaj se zgodi, če funkciji kot vhodni parameter podamo datoteko, ki ne obstaja.
• kaj se zgodi, če vhodna datoteka ni podana v ustrezni obliki.