|
OKusat cu se u objasnjavanju, valjda ce pomoc :)
Retci matrice predstavljaju predmete, a stupci dopusteni kapacitet. Dakle, ako gledas elemente u drugom retku, znaci da rezultati predstavljaju optimalne rezultate ukoliko su koristeni samo prvi i drugi predmet (dakle, uz pretpostavku da mozemo samo njih uzeti). Isto tako, peti stupac znaci da su to rezultati uz pretpostavku da ne zelimo napuniti ruksak iznad kapaciteta 5 (nego nam je 5 maksimalni kapacitet).
Element na mjestu (i, j) u matrici oznacava maksimalnu vrijednost koju mozemo ponijeti u rancu kapaciteta j uz uvjet da mozemo uzeti samo predmete iz skupa prvih i predmeta.
Ideja algoritma je da izracunamo najvecu vrijednost koju mozemo ponijeti u rancu za prvih i predmeta i svaki moguci kapacitet do zadanog maksimalnog kapaciteta, kada to imamo, nije nam vazan put kojim smo dosli do toga (dakle koje smo predmete uzeli i koliko smo stvarno kapaciteta ranca zauzeli - uostalom i ti se podaci mogu iscitati iz matrice), nego samo maksimalna vrijednost za svaki od kapaciteta i predmeta.
Tada gledamo za i + 1-vi predmet, koji tezine w i vrijednosti p. Ocito za kapacitete ruksaka manje od w, ne mozemo staviti taj predmet u ruksak, pa nam je najveca vrijednost koju mozemo uzeti ista kao i za prvih i. Za ostale kapacitete ranca gledas sto ti se vise isplati, staviti i+1-vi predmet u ranac kapaciteta j, ili radije ostaviti isti raspored koji smo imali sa prvih i predmeta. Ako stavljas predmet u ranac, vrijednost koju ces dobiti bit ce p + M[i, j-w) zato sto dobivas vrijednost p od novog predmeta, a moras imati w slobodnog prostora u rancu a M(i, j-w) je upravo maksimalna vrijednost koju mozes imati u rancu popunjenom do kapaciteta j-w predmetima iz skupa prvih i. Ako ne stavljas novi predmet, onda ti je maksimalna vrijednost ona ista koju imas sa prvih i predmeta, dakle M(i, j).
Nadam se da je sad malo jasnije :)
OKusat cu se u objasnjavanju, valjda ce pomoc 
Retci matrice predstavljaju predmete, a stupci dopusteni kapacitet. Dakle, ako gledas elemente u drugom retku, znaci da rezultati predstavljaju optimalne rezultate ukoliko su koristeni samo prvi i drugi predmet (dakle, uz pretpostavku da mozemo samo njih uzeti). Isto tako, peti stupac znaci da su to rezultati uz pretpostavku da ne zelimo napuniti ruksak iznad kapaciteta 5 (nego nam je 5 maksimalni kapacitet).
Element na mjestu (i, j) u matrici oznacava maksimalnu vrijednost koju mozemo ponijeti u rancu kapaciteta j uz uvjet da mozemo uzeti samo predmete iz skupa prvih i predmeta.
Ideja algoritma je da izracunamo najvecu vrijednost koju mozemo ponijeti u rancu za prvih i predmeta i svaki moguci kapacitet do zadanog maksimalnog kapaciteta, kada to imamo, nije nam vazan put kojim smo dosli do toga (dakle koje smo predmete uzeli i koliko smo stvarno kapaciteta ranca zauzeli - uostalom i ti se podaci mogu iscitati iz matrice), nego samo maksimalna vrijednost za svaki od kapaciteta i predmeta.
Tada gledamo za i + 1-vi predmet, koji tezine w i vrijednosti p. Ocito za kapacitete ruksaka manje od w, ne mozemo staviti taj predmet u ruksak, pa nam je najveca vrijednost koju mozemo uzeti ista kao i za prvih i. Za ostale kapacitete ranca gledas sto ti se vise isplati, staviti i+1-vi predmet u ranac kapaciteta j, ili radije ostaviti isti raspored koji smo imali sa prvih i predmeta. Ako stavljas predmet u ranac, vrijednost koju ces dobiti bit ce p + M[i, j-w) zato sto dobivas vrijednost p od novog predmeta, a moras imati w slobodnog prostora u rancu a M(i, j-w) je upravo maksimalna vrijednost koju mozes imati u rancu popunjenom do kapaciteta j-w predmetima iz skupa prvih i. Ako ne stavljas novi predmet, onda ti je maksimalna vrijednost ona ista koju imas sa prvih i predmeta, dakle M(i, j).
Nadam se da je sad malo jasnije
_________________
Bri
|
