Pretpostavimo da raspolažemo pravokutnom čeličnom pločom dimenzija ax b centimetara i strojem koji može prepiliti tu ploču u dvije nove pravokutne ploče, dimenzija a1 x b i a2 x b (gdje je a1+ a2 =a) odnosno a x b1 i a x b2 (gdje je b1 + b2 = b), ovisno o smjeru rezanja (horizontalno ili vertikalno). Nove dimenzije a1 i b1, odnosno a2 i b2, možemo odabrati po želji.

Radi jednostavnosti pretpostavite da su a, b, a1, a2, b1, b2 ϵ N (prirodni brojevi).

Zadatak je izrezati ploču početnih dimenzija a x b u manje ploče od kojih svaka ima jednu od sljedećih triju veličina: 100 x150, 180x200 i 50 x120. Cijene po kojima možemo prodati izrezane ploče ovih vrsta su 12, 36 i 7 eura, redom. Koristeći dinamičko programiranje, opišite postupak za maksimizaciju profita izrezivanjem ploča zadanih veličina iz početne ploče.

 Uputa: u svakom potproblemu moramo donijeti dvije odluke, hoćemo li rezati vertikalno ili horizontalno te na kojem mjestu. Označimo li sa C(a, b) ukupan profit koji možemo dobiti izrezivanjem ploče dimenzija ax b, tada vrijedi:

C(a, b) = [ C(j , b) + C(a- j , b) ako režemo po širini i

[ C(a, j) + C(a, b ¡ j) ] ako režemo po dužini

Pritom je j cijeli broj između 1 i a - 1 odnosno 1 i b - 1 (uključivo).

Ako želimo maksimizirati profit, moramo birati veću od gornje dvije vrijednosti. Kako izgledaju bazni slučajevi u kojima više ne režemo dalje? Kako računamo profit za bazne slučajeve?

Napišite program u Matlabu koji za dane a i b računa maksimalan profit. Izračunate vrijednosti C(i. j) trebaju se pohraniti u matricu dimenzija ax b (širina i dužina početne ploče) na poziciji (i, j) kako bi se spriječilo opetovano rekurzivno izračunavanje te iste vrijednosti. Tu matricu kreirajte pomoću ključne riječi persistent.