Pretraživanje na karti

karta

Matematika

Dinamičko programiranje

Istaknuto · Pitanje postavio/la Sonja (Gost)
u Srijeda, Kolovoz 30 2023, 01:09 ·

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.

 

Nema dodijeljene oznake
  • Ne postoji odgovor na ovo pitanje.

Dodaj odgovor Vaš odgovor

Istaknite svoj oglas i povećajte posjećenost do 6 puta

Stranica Moje Instrukcije za vrijeme školske godine bilježi preko 100 000 posjeta mjesečno, stoga nemojte propustiti priliku i popunite svoje slobodne termine s nama.

Imate objavljen oglas, istaknite ga:

  1. prijavite se na stranicu
  2. na oglasu kliknete na "Istaknite svoj oglas"
  3. sljedite jednostavne upute

Detaljniji opis i cjenik

classroom

Pišite lekcije i povećajte posjećenost svog oglasa

Pišite kratke lekcije i pomognite djeci u njihovoj potrazi za znanjem, a vaš oglas će biti prikazan u vrhu lekcije koju ste napisali. Na taj način možete i jednostavno dogovoriti instrukcije umjesto da vas traže preko tražilice u moru ostalih instruktora.

Detaljnije

Predajte novi oglas Istaknite svoj oglas i povećajte posjećenost do 6 puta

Novo! Imate pitanje? Postavite ga ovdje! Postavite pitanje Instruktori, odgovarajte na pitanja, jer su odgovori i komentari povezani sa Vašim oglasom
Trenutno aktivnih Gostiju: 93