Ako je broj duzina koje se trebaju dobiti mali, onda mozesh da problem reshish i bektrekom.
Resenje dinamickim programiranjem bi moglo da ide ovako:
neka nam je N broj ulaznih shipki (sa n cemo obelezavati njihovu duzinu), a M broj
trazenih duzina. Neka X
i, i=1..M, je i-ta trazena duzina. Neka V[i,k,j] znachi da
popunjavamo prvih i shipki, sa prvih j duzina, tako da nam je u i-toj shipki popunjeno k
mesta. V[i,k,j] moze imati vrednost 0(sto znaci da smo sve sipke od 1 do i-1 popunili sa
zadovoljavajucim ostatkom) ili 1(sto znaci da smo popunjavajuci neke od shipki dobili
nezadovoljavajuci ostatak ili nismo uopste stigli do ovakve situacije). Ako nam je
poznato neko V[i,k,j], mi mozemo izracunati i sledece vrednosti:
ako je v[i,j,k]=0 i k<100 ili k>600 onda v[i+1,x[j],j+1]:=v[i,j,k];
ako je v[i,j,k]=0 i k>=x[j] onda v[i,k-x[j],j+1]:=v[i,j,k];
Na pocetku postavish vrednost V[1,n,0]:=0, i redom popunjavash. Na kraju pogledash
koja od vrednosti V[N,k,M], k=0..200, 600... ima vrednost 0, i na osnovu nje
rekonstruishesh gde si koju duzinu sekao.
Ovo moze lako da se prosiri tako da dobijesh reshenje koje ce ti davati i najmanji otpad
(znachi od svih zadovoljavajucih otpada, dobijash najmanji).
Ako ti neshto nije jasno (ili ako uvidish da sam ja mozda neshto pogreshno napisao),
reci, pa cu probati da razjasnim :)
[edit] I usput sam shvatio da sam, onako, bash lupio :)
[Ovu poruku je menjao RooTeR dana 11.09.2005. u 02:04 GMT+1]
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Verovatno varjanta "Problema ranca" (knapsack problem)
