  ̌      ̌   
P 48 (2020/2021) 5 25
Dinamično programiranje in
problem nahrbtnika
I M̌
Dinamično programiranje je metoda reševanja
določenih problemov, ko iščemo najboljši rezultat,
npr. najkrajšo pot ali največjo nagrado. Problemi,
ki jih lahko rešimo tako, da jih razbijemo na manj-
še, poiščemo najboljšo rešitev le-teh in te rešitve
združimo v rešitev večjega problema, so zelo pri-
merni za dinamično programiranje. Če se nekateri
podproblemi prekrivajo, potem uporaba dinamič-
nega programiranja močno pospeši algoritem za re-
ševanje.
Zgodovina in poimenovanje
Izvor imena dinamično programiranje je nenavaden
in zanimiv. Kot bomo videli, ni pri dinamičnem pro-
gramiranju nič preveč dinamičnega, metoda pa tudi
ni neposredno povezana s programiranjem, saj gre
pravzaprav za matematično tehniko. Dinamično pro-
gramiranje je v petdesetih letih prejšnjega stoletja
razvil ameriški matematik Richard Bellman in v svoji
avtobiografiji [1] opisal razlog za čudno poimenova-
nje. Petdeseta leta niso bila najboljša za financira-
nje matematičnih raziskav. Da bi Bellman pridobil
financiranje ministrstva za obrambo, je moral s pri-
merno izbranim imenom zakriti, kaj bo v resnici po-
čel. S svojo tehniko je želel reševati probleme op-
timalnega načrtovanja. A besedo načrtovanje je za-
menjal z besedo programiranje. Ker je želel opisati,
da se metoda dogaja v več korakih, je izbral še be-
sedo dinamično, delno zato, ker že ima močan fizi-
kalen pomen, in delno zato, ker jo je težko uporabiti
v zaničevalnem smislu. Z besedno zvezo dinamično
programiranje je bil zadovoljen, saj je bila dovolj ge-
nerična, da poslanci in ministri niso ugovarjali; finan-
ciranje raziskav je bilo tako zagotovljeno.
Ilustrativni primer
Osnovni primer dinamičnega programiranja, ki kaže
strukturo ponavljajočih podproblemov, je izračun n-
tega Fibonaccijevega števila. Spomnimo se, da so Fi-
bonaccijeva števila definirana z zvezo
F0 “ 1, F1 “ 1, Fn “ Fn´1 ` Fn´2,
torej je vsako naslednje število vsota prejšnjih dveh,
pri čemer začnemo z 1, 1. Če bi funkcijo za izračun
n-tega števila napisali kot
def fib(n):
if n <= 1: return 1
else: return fib(n-1) + fib(n-2)
in izračunali fib(5), bi dobili zaporedne klice:
fibp5q “ fibp4q ` fibp3q
“ pfibp3q ` fibp2qq ` pfibp2q ` fibp1qq
“ ppfibp2q ` fibp1qq ` pfibp1q`
`fibp0qqq`ppfibp1q`fibp0qq`fibp1qq
“ pppfibp1q ` fibp0qq ` fibp1qq`
` pfibp1q ` fibp0qqq ` ppfibp1q`
` fibp0qq ` fibp1qq
V zadnjem izračunu, vidimo, da se kar trikrat ponovi
izračun fib(2), kot označeno z zvezdico:
pppfibp1q`fibp0qq
loooooooooomoooooooooon
˚
f̀ibp1qq ` pfibp1q`fibp0qq
loooooooooomoooooooooon
˚
q`
` ppfibp1q ` fibp0qq
looooooooooomooooooooooon
˚
`fibp1qq.
  ̌      ̌   
P 48 (2020/2021) 526
To je primer manjšega podproblema enake oblike.
Zato, da bi izračunali fib(5), moramo izračunati
fib(3) in fib(4), za ta dva pa potrebujemo fib(3),
fib(2) (dvakrat) in fib(1). Vidimo, da bi fib(3)
in tudi fib(2) pri različnih podproblemih računali
večkrat; to je druga lastnost, ki omogoča uporabo
dinamičnega programiranja (manjši podproblemi se
prekrivajo). Popolnoma nepotrebno in računsko po-
tratno je vsakič znova ponavljati enak izračun za
fib(2). Dovolj je le, da ga izračunamo samo enkrat
in si zapomnimo rezultat. Ko za fib(5) potrebu-
jemo fib(4) in fib(3), najprej računamo fib(4).
Za to potrebujemo fib(3) in fib(2) in najprej izra-
čunamo fib(3). Za to potrebujemo fib(2) in
fib(1). Zopet najprej izračunamo fib(2), za kar
potrebujemo fib(1) in fib(0), ki ju oba že pozna-
mo, ju seštejemo in dobimo fib(2) = 2. S tem smo
izračunali prvi del izračuna za fib(3), drugi del,
fib(1), pa poznamo po definiciji in tako dobimo
fib(3) = 3. S tem smo dobili prvi del izračuna za
fib(4). Lotimo se računanja drugega dela fib(2).
To smo že izračunali: rezultat je enak 2, tako dobimo
fib(4) = 5. S tem smo izračunali prvi del za izra-
čun fib(4), drugi del pa zahteva izračun fib(3).
Vemo, da je rezultat 3 in dobimo fib(5) = 8.
Alternativni način računanja, ki je morda v tem
primeru lažji, je, da računamo od »spodaj«. Ker ve-
mo, da bomo potrebovali vrednosti fib od 0 do 5,
jih lahko računamo kar po vrsti, tako da jih imamo
vedno na voljo, ko bo potrebno. Če računamo tako,
dobimo
fibp0q “ 1
fibp1q “ 1
fibp2q “ fibp1q ` fibp0q “ 1 ` 1 “ 2
fibp3q “ fibp2q ` fibp1q “ 2 ` 1 “ 3
fibp4q “ fibp3q ` fibp2q “ 3 ` 2 “ 5
fibp5q “ fibp4q ` fibp3q “ 5 ` 3 “ 8.
V obeh primerih se izognemo dodatnim izračunom.
Za izračun fib(100) bi potrebovali več ur, za izra-
čun s pomočjo dinamičnega programiranja pa potre-
bujemo le nekaj milisekund.
Problem nahrbtnika
Oglejmo si še en problem, pri reševanju katerega
nam uporaba dinamičnega programiranja da opti-
malno rešitev. Predstavljajmo si, da smo v vlogi ro-
parja, ki ima s sabo samo en nahrbtnik z omejeno
prostornino, iz zlatarne pa želi odnesti čim več pred-
metov. Kako izbrati predmete?
Podajmo problem malo natančneje in bolj rigoro-
zno: dan imamo nahrbtnik, v katerega lahko damo
največ W kilogramov, in n predmetov s celoštevil-
skimi masamiw1, . . .wn, ki so vredni p1, . . . , pn. Naš
cilj je zložiti predmete v nahrbtnik tako, da bomo
v njem imeli največjo vrednost predmetov, seveda
upoštevajoč, da je skupna masa predmetov v nahrb-
tniku manjša ali enaka W . Pri tem predmetov ne
smemo deliti: za vsak predmet se odločimo, ali ga
vzamemo ali ne. Tak problem nahrbtnika se imenuje
tudi 0-1 nahrbtnik.
Morda najprej pomislimo, da bi predmete razvr-
stiti glede na razmerje vrednosti in mase piwi tako,
da so na začetku tisti, ki imajo največ »vrednosti na
kilogram«. Taki rešitvi rečemo požrešna, nas pa ne
pripelje vedno do optimalne odločitve. Oglejmo si
primer.
Recimo, da imamo nahrbtnik, v katerega lahko zlo-
žimo W “ 5 kilogramov, na voljo pa imamo tri pred-
mete, katerih masa in vrednost sta prikazana v
tabeli 1.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
predmet 3 4 2 2
predmet 2 7 3 2,33. . .
predmet 1 10 4 2,5
vrednost masa razmerje
TABELA 1.
Prikazan je primer 0-1 nahrbtnika z omejitvijo W “ 5, kjer po-
žrešna strategija ne deluje.
Če predmete razvrstimo padajoče po razmerju
med vrednostjo in maso, ima prvi predmet najboljše
razmerje 10{4 “ 2,5, nato drugi predmet z razmer-
jem 7{3 « 2,33, najmanjše razmerje pa ima tretji
predmet 4{2 “ 2. Če torej vzemamo predmete po vr-
sti, v nahrbtnik pospravimo prvi predmet, masa na-
šega nahrbtnika je zdaj 4 kilograme, vrednost pa 10.
Drugega predmeta ne moremo več vzeti, saj bi sku-
pna masa bila 4 ` 3 “ 7, kar je več kot 5 kilogramov,
kar je naša omejitev.
  ̌      ̌   
P 48 (2020/2021) 5 27
Vendar pa to ni najboljša rešitev, ki jo lahko dose-
žemo s temi predmeti. Če namreč vzamemo drugi in
tretji predmet, bo skupna masa našega nahrbtnika
še ravno dovoljenih 5 kilogramov, vrednost pa bo 11.
Požrešen pristop nas v tem primeru ni pripeljal do
prave rešitve.
Ali se lahko problema lotimo z dinamičnim pro-
gramiranjem? Poskusimo najti rešitev s pomočjo re-
šitve manjših podproblemov. Lahko se omejimo na
manjše število predmetov, namesto da upoštevamo
vse predmete naenkrat, in se vprašamo, kakšna bi
bila optimalna vrednost, če bi imeli na voljo le en
predmet, dva predmeta ipd. Poleg tega lahko kot na
podproblem gledamo tudi, če je volumen nahrbtnika,
ki ga imamo na voljo, manjši.
Označimo optimalno vrednost problema nahrbtni-
ka z omejitvijo w kilogramov in upoštevajoč pred-
mete 1, . . . , i s kpw, iq. Za naš primer si zamislimo
najbolj enostaven podproblem: recimo, da imamo na
voljo le 1 kilogram prostora v našem nahrbtniku, to-
rej w “ 1. Vsi trije naši predmeti imajo maso večjo
od 1, torej v nahrbtnik ne moremo spraviti nobenega
izmed njih. Optimalne vrednosti so torej enake 0 ne
glede na to, koliko predmetov upoštevamo (samo pr-
vega, prvega in drugega, vse tri):
kp1,1q “ kp1,2q “ kp1,3q “ 0.
Povečajmo prostornino našega nahrbtnika za 1, to-
rej w “ 2. Če upoštevamo prvi predmet, ali pa prvi
in drugi predmet, bo optimalna vrednost nahrbtnika
enaka 0, saj sta oba predmeta pretežka. Če pa upo-
števamo vse tri predmete, lahko v nahrbtnik spra-
vimo le tretji predmet. Optimalna vrednost bo v tem
primeru torej p3 “ 4:
kp2,1q “ kp2,2q “ 0, kp2,3q “ 4.
Za omejitev w “ 3 je prvi predmet še vedno preve-
lik. Če upoštevamo prva dva predmeta, je optimalna
vrednost ravno vrednost drugega predmeta:
kp3,1q “ 0, kp3,2q “ p2 “ 7.
Kaj pa, če upoštevamo vse tri predmete? Sedaj ima-
mo dva predmeta, ki bi šla v naš nahrbtnik (drugi
predmet in tretji predmet). Vzamemo največjega, to-
rej drugi predmet. Poglejmo še drugače: rešitev, ki
upošteva vse tri predmete, lahko sestavimo iz reši-
tve, ki upošteva prva dva. Torej se pravzaprav od-
ločamo, ali želimo tretji predmet dati v nahrbtnik
ali ne. Če ga damo, potem je preostala prostornina
nahrbtnika še 1, torej je vrednost nahrbtnika v tem
primeru seštevek vrednosti tretjega predmeta in op-
timalne vrednosti za podproblem z omejitvijo nahrb-
tnika 1, upoštevajoč prvi in drugi predmet. Če pa ga
ne dodamo v nahrbtnik, imamo na voljo še vse 3 kilo-
grame, vrednost našega nahrbtnika je kar optimalna
vrednost podproblema za w “ 3, upoštevajoč prvi
in drugi predmet. Optimalna vrednost bo seveda ma-
ksimum obeh dveh vrednosti:
kp3,3q “ maxt kp1,2q ` p3
loooooomoooooon
vzamemo predmet 3
,
ne vzamemo predmeta 3
hkkikkj
kp3,2q u
“ maxt0 ` 4, 7u “ 7.
Na hitro si poglejmo še optimalne vrednosti za w “
4. Ko upoštevamo le prvi predmet, ga seveda vza-
memo, v nahrbtnik pa potem ne moremo spraviti
ničesar več. Če upoštevamo prvi in drugi predmet,
ugotovimo, da lahko v nahrbtnik spravimo le enega
od teh dveh, torej je bolje vzeti vrednejšega, to je
prvi predmet. Podobno ugotovimo, ko upoštevamo
vse tri, torej
kp4,1q “ kp4,2q “ kp4,3q “ p1 “ 10.
Sedaj lahko rešimo naš primer za omejitev, ki nas
res zanima, w “ 5. Če upoštevamo le prvi predmet,
ga vzamemo; vrednost našega nahrbtnika je 10. Če
upoštevamo prva dva predmeta, se torej odločamo,
ali bi vzeli drugega, pri čemer bi v nahrbtniku ostala
2 kilograma prostora, kar ne bi bilo dovolj za prvega,
ali drugega predmeta ne bi vzeli, v tem primeru bi
torej vzeli optimalno rešitev podproblema za w “ 5,
ki smo ga ravnokar izračunali. Ker ima prvi pred-
met precej boljšo vrednost, je maksimum dosežen
pri drugi opciji. Sedaj poglejmo še, kako je, če upo-
števamo vse tri predmete. Odločamo se, ali izbrati
tretji predmet ali ne. Če ga izberemo, potem imamo
na voljo še 3 kilograme, vrednost našega nahrbtnika
je torej seštevek vrednosti tretjega predmeta p3 in
optimalne rešitve podproblema nahrbtnika z omeji-
  ̌      ̌   
P 48 (2020/2021) 528
tvijo w “ 3, upoštevajoč prva dva predmeta:
kp5,1q “ p1 “ 10,
kp5,2q “ maxtkp2,1q ` p2, kp5,1qu
“ maxt0 ` 7,10u “ 10,
kp5,3q “ maxtkp3,2q ` p3, kp5,2qu
“ maxt7 ` 4,10u “ 11.
Optimalne rešitve vseh podproblemov lahko tabeli-
ramo, kar je prikazano v tabeli 2. Odgovor na naše
vprašanje se skriva desno spodaj, kjer je vrednost
nahrbtnika upoštevajoč vse predmete in začetno po-
dano omejitev mase.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
5 10 10 11
4 10 10 10
3 0 7 7
2 0 0 4
1 0 0 0
w\i 1 2 3
TABELA 2.
Tabela optimalnih rešitev podproblemov (vrednosti kpw, iq) za
izbrani primer 0-1 nahrbtnika.
Sedaj razmislimo o problemu v splošnem in po-
skusimo ugotoviti, kako se manjši problemi upora-
bijo za reševanje večjega ter poskusimo zapisati
splošno rekurzivno formulo. Spomnimo se, da s
kpw, iq označimo optimalno vrednost problema na-
hrbtnika z omejitvijo w kilogramov in upoštevajoč
predmete 1, . . . , i, pri čemer imamo skupaj N pred-
metov. Vrednost kpw, iq želimo izračunati s pomo-
čjo rešitve podproblemov za različne omejitve nahrb-
tnikov, kjer upoštevamo samo predmete do i ´ 1.
Predstavljajmo si torej, da že imamo rešitve vse pod-
problemov, kjer upoštevamo samo predmete do i´1,
za različne omejitve nahrbtnikov od 1 do w.
Na tej točki se želimo odločiti, ali vzeti predmet
i ali ne. Če se odločimo, da predmeta ne vzamemo,
potem je naša vrednost nahrbtnika enaka vrednosti
nahrbtnika kpw, i ´ 1q z omejitvijo w, upoštevajoč
predmete do i ´ 1. Če predmet vzamemo, potem
imamo v nahrbtniku le še w ´ wi prostora, torej je
vrednost našega nahrbtnika enaka seštevku vredno-
sti predmeta pi in vrednosti nahrbtnika kpw´wi, i´
1q. Izberemo tisto izmed možnosti, ki da večjo vre-
dnost nahrbtnika. Pri tem moramo upoštevati, da
je možnost, da predmet vzamemo, na voljo le, če
nam omejitve nahrbtnika to dopuščajo: veljati mora
namreč w ě wi, sicer je edina možnost, da ga pu-
stimo. Formula za izračun optimalne vrednosti je
tako enaka
kpw, iq“
$
’
’
’
’
&
’
’
’
’
%
maxtkpw, i´1q, kpw´wi, i´1q`piu,
če w ě wi
kpw, i´ 1q,
sicer
(1)
Za popolno rešitev moramo razmisliti še o končnih
pogojih. Podobno kot v primeru, ki smo ga obrav-
navali prej, je vrednost nahrbtnika z omejitvijo teže
0 enaka 0, saj ne moremo vanj shraniti nobenega
predmeta. Prav tako je vrednost nahrbtnika enaka
0, če nimamo na voljo nobenega predmeta ne glede
na kapaciteto, ki je na voljo. Zapisano s formulami
so robni pogoji enaki
kpw,0q “ 0 za vse w od 0 do W
kp0, iq “ 0 za vse i od 0 do N (2)
Rešitev lahko zapišemo tudi s pomočjo programske
kode, ki tesno sledi zgornji razlagi. Funkcija
knapsack spodaj sprejme omejitev W , seznam tež
predmetov weights, ki hraniw1, . . . ,wN , ter seznam
vrednosti predmetov prices, ki hrani vrednosti
p1, . . . , pN . Vrednosti kpw, iq izračunamo za vsew “
0, . . . ,W in i “ 0, . . . ,W . Za začetek si pripravimo
prazno tabelo, v katere bomo vpisovali vrednosti
kpw, iq. Nato v dveh zankah nastavimo robne po-
goje pri i “ 0 in w “ 0, kot smo opisali v enačbi (2).
Na koncu po vrsti izračunamo še vse ostale vredno-
sti kpw, iq, pri čemer jih računamo s pomočjo for-
mule (1). Pri tem vrednosti računamo v pravem vr-
stnem redu, tako da sta pri računanju k[w][i] manj-
ša podproblema k[w][i-1] in k[w-w_i][i-1] že iz-
računana.
def knapsack(W, weights, prices):
N = len(weights)
k = [[None for _ in range(N+1)] for _
in range(W+1)]
for i in range(N+1):
     
P 48 (2020/2021) 5 29
k[0][i] = 0
for w in range(W+1):
k[w][0] = 0
for w in range(1, W+1):
for i in range(1, N+1):
w_i, p_i = weights[i-1],
prices[i-1]
if w_i > w:
k[w][i] = k[w][i-1]
else:
k[w][i] = max(k[w][i-1],
k[w-w_i][i-1] + p_i)
return k[W][N]
Ta tehnika računanja reši problem v približno W ¨
N korakih, kar je precej bolj učinkovito, kot če bi
preverili vse možnosti. Bralci ste tudi spodbujeni,
da preverite, ali podana programska koda izračuna
enake številke, kot so dane v tabeli 2. Lahko pa po-
skusite rešiti primer z npr. petimi ali več predmeti in
se prepričate o pravilnosti in enostavnosti postopka.
Literatura
[1] R. Bellman, Eye of the Hurricane: An Autobio-
graphy, World Scientific, 1984.
ˆ ˆ ˆ
Rešitev
nagradne
uganke
B̌ K
Bralcem smo v članku 21 aritmetičnih vprašanj
o številu 2021 v prejšnji številki zastavili naslednjo
uganko: Za katera naravna števila n se število n! v
običajnem desetiškem zapisu konča z natanko 2021
ničlami? Do 14. marca 2021 smo v uredništvu pre-
jeli dve rešitvi, obe pravilni: iskano število sploh ne
obstaja. Uspešna reševalca Ivan Lisac iz Kopra in An-
drej Jakobčič iz Novega mesta bosta za nagrado pre-
jela knjigo o teoriji števil iz ponudbe DMFA – zalo-
žništva. Rešitev, do katere lahko pridemo tudi brez
računalnika, je zapisana v nadaljevanju.
Označimo število končnih ničel števila n! z ozna-
ko tpnq. Kot je bilo opisano že v članku, je število
tpnq enako eksponentu prafaktorja 5 v prafaktoriza-
ciji števila n!, saj vsaka končna ničla nastane z mno-
ženjem para prafaktorjev 2 in 5. Ker je med 1 in
n natanko rn5 s večkratnikov števila 5, natanko r
n
52 s
večkratnikov števila 25 in tako dalje, lahko za dani
n vrednost tpnq izračunamo po De Polignacovi (ozi-
roma Legendrovi) formuli tpnq “
ř8
k“1
”
n
5k
ı
.
Da bi določili število n z lastnostjo tpnq “ 2021,
je potrebno razmišljati v obratno smer. Števila n se-
veda ni mogoče direktno izraziti iz enačbe. Ker pa
za funkcijo celi del velja rxs ď x, lahko z uporabo
formule za vsoto geometrijske vrste dobimo oceno
tpnq “ 2021 ă
8
ÿ
k“1
n
5k
“ n
5
8
ÿ
k“0
ˆ
1
5
˙k
“ n
5
¨ 1
1 ´ 15
“ n
4
oziroma n ą 8084. Za n “ 8085 zdaj z uporabo
De Polignacove formule dobimo tp8085q “ 2018, to-
rej je treba n nekoliko povečati. Opazimo lahko, da
zaradi preštevanja večkratnikov števila 5 velja, da je
tpnq ą tpn ´ 1q, če je n večkratnik števila 5, sicer
pa je tpnq “ tpn ´ 1q. Zato hitro ugotovimo, da je
tp8090q “ . . . “ tp8094q “ 2019 in tp8095q “ . . . “
tp8099q “ 2020, toda tp8100q “ 2022, saj je 8100
deljivo s 25. Dokazali smo, da iskano število n ne
obstaja.
Omenimo še, da lahko ročno računanje z De Poli-
gnacovo formulo precej pohitrimo z uporabo znane
zveze rn{pabqs “ rrn{as{bs, po kateri lahko rekur-
zivno izračunamo izraze oblike rn{pks. Za števili
n “ 8085 in p “ 5 dobimo denimo r8085{5s “ 1617,
r8085{52s “ r1617{5s “ 323, r8085{53s “ r323{5s “
64, r8085{54s “ r64{5s “ 12, r8085{55s “ r12{5s “ 2
in r8085{56s “ r2{5s “ 0, od koder sledi tp8085q “
1617 ` 323 ` 64 ` 12 ` 2 ` 0 “ 2018.
ˆ ˆ ˆ