REZANJE  VERIG

 

Potnik ima zlato verižico z sedmimi členi. Dogovori se, da plača najemnino po menjalnem tečaju en člen na dan. Dogovoril se je, da mu člene lahko tudi vrnejo. Najemnino mora plačevati dnevno, toda želi si, da bi njegova verižica ostala čim bolj nedotaknjena. Kolikšno je najmanjše število rezov, ki jih mora narediti? Poznamo še druge verzije tega problema z 23, 50 in 63 členi.

Privzamemo, da ko je člen prerezan, ga lahko ločimo od obeh sosedov in ga tako lahko odstranimo iz verige. Torej: člene moramo prerezati tako, da če jih postavimo v vrsto, bo ta vrsta vsebovala vsa cela števila od 1 do največjega števila členov. Vsako rezanje verige, pri katerem bo število rezov minimalno, bomo imenovali optimalno rezanje. Za optimizacijo sta potrebna dva dela:

1.   število prerezanih členov mora biti minimalno

2.   členi morajo biti prerezani tako, da zadostijo zahtevam naloge

 

Veriga s 7 členi: prerezati moramo 3. člen

 

Prvi dan damo enega, drugi dan nam prvega vrnejo in damo dva člena. Tretji dan dodamo en člen, četrti dan vrnejo tri, mi damo štiri člene. Peti dan damo en člen. Šesti dan vrnejo en člen, mi damo dva, sedmi dan damo še en člen.

 

Sedaj se bomo ukvarjali z optimalnim rezanjem verige z poljubnim številom členov.

Način dela:

Posamezne člene bomo označili z   , kjer j pomeni mesto člena v prvotni verigi ( od fiksnega konca ). Verigo, ki vsebuje k členov, bomo označili z Ck  . Podveriga dane verige je sestavljena iz enega ali več neprerezanih členov, ki smo jih dobili z odstranitvijo enega ali več členov iz prvotne verige. Takšno podverigo bomo označili z   Sj     j= 1, 2, 3,...

Dolžina podverige je število členov, ki jih vsebuje, označimo jo z       . Očitno je dovolj za to, da definiramo optimalni rez, če povemo dolžino vsake podverige.

C7:  ali ,   

 

Naloga:

Kolikšna je maksimalna dolžina verige m, da bo  Cm      optimalno prerezana z n rezi?

Če imamo na voljo natanko n rezov, potem imamo natanko n posameznih členov, ki so nam na voljo. Očitno lahko dobimo vsa cela števila od 1 do n z uporabo teh posameznih členov, torej mora obstajati vsaj ena podveriga, ki vsebuje vsaj en, toda ne več kot n+1 členov ali drugače povedano: števila n+1 na moremo dobiti ( iz teh posameznih členov ). Ker si želimo obdržati število rezov na minimumu, bomo uporabili najdaljšo podverigo, torej postavimo            in prvi rez lahko naredimo pri  . Sedaj lahko dobimo vsa cela števila do n+n+1=2n+1. Naslednja podveriga, torej ne sme vsebovati več kot 2n+2 členov. Ker želimo, da bi bil m največji možen, postavimo    in naslednji rez  bo pri    .                  

 

Podobno                                       

Ker dolžina vsake od naslednjih podverig ne sme biti večja od seštevka dolžin prejšnjih podverig +n( število rezov )+1 sledi     za j= 1,...,n+1, da dobimo največji možen m.

Najdaljša podveriga

 

m =(n+1) 2n+1-1.