5. naloga

Zlaganje loncev


V kuhinjsko omaro zlagamo lonce. Lonci so v obliki odprtih valjev različnih premerov. Zaradi prihranka prostora lahko natanko en manjši lonec položimo v večjega, kadar ima manjši premer osnovne ploskve kot večji lonec. V ta manjši lonec pa lahko kasneje položimo še en manjši lonec in tako naprej, da dobimo nekakšen sklad loncev. Ne želimo pa v en lonec neposredno postaviti dveh ali več manjših (npr. da bi v lonec premera 20 cm postavili neposredno lonca premerov 5 cm in 3 cm; v tem primeru bi v lonec premera 20 cm postavili lonec premera 5 cm, v slednjega pa potem lonec premera 3 cm). Želimo preveriti, ali je naša kuhinjska omara dovolj prostorna, da lahko v njo na ta način postavimo vse svoje lonce.

Opiši postopek (ali napiši program ali podprogram oz. funkcijo, če ti je lažje), ki kot vhodni podatek dobi seznam premerov vseh loncev na kuhinjski mizi ter izračuna najmanjše število skladov, ki jih lahko sestavimo iz teh loncev. Izračuna pa naj tudi najnižjo možno vsoto, ki jo lahko dobimo, če vzamemo premer najbolj spodnjega lonca v vsakem skladu in te premere seštejemo po vseh skladih. Dobro tudi utemelji pravilnost svojega postopka.

Primer: če imamo lonce s premeri

28, 17, 14, 29, 12, 22, 28, 28, 13, 20, 30, 18, 4, 18, 4,

potrebujemo najmanj tri sklade, najmanjša možna vsota premerov pa je 86. (Eden od možnih načinov, kako lahko zložimo lonce na optimalen način, so takšni trije skladi: [4, 14, 28, 29, 30], [13, 17, 18, 28] in [4, 12, 18, 20, 22, 28]; vsota premerov najbolj spodnjih loncev je takrat 30 + 28 + 28 = 86.)