Uf, zanimljivo je ovo dinamicko programiranje, Danilo je bio u pravu, kada nije definisan problem do kraja zna da bude bas zanimljivo :)
Dakle jel mozete za nas sa jeftinijim ulaznicama da ponovite zadatak, ali ovog puta ispravno sa jednim ili bar dva priemra, naravno ako moze, sto metoda grube sile ne bi bila dobra ???
Bijeli_dedA:
A šta se tiče onog primjera, pogledaj i sam da je moj dobar. [1,2,1] JE podniz drugog, a [1,1,2] NIJE (vidi ispravku ispravka zadatka :) koju je napisao Lucky).
Da li je u onom primeru n1 PRVI niz, a n2 DRUGI niz? Ako jeste, onda samo jos jedno pitanje: da li ti nas ovde zavitlavas?
Deda, moje izvinjenje. Imao sam pogresnu predstavu o tome sta se smatra podnizom datog niza...sorry.
Nesto o samom problemu. Backtracking...i jeste i nije primena grube sile. Jeste, zato sto, u principu, isprobavas moguce kombinacije; nije, zato sto uvodis neke uslove koji skracuju moguce "staze" ili odbacuju citave "grane" u trazenju pravog resenja. Stos je, jasno, u tim uslovima, i mislim da se to ovde moze iskoristiti.
Pozdrav
Brute-Force ne dolazi u obzir osim kao poslijednja opcija, a ja mislim da jedan broj ne moze biti podniz nego je on samo clan niza, ne znam mozda nisam u pravu :|. A evo ovako da ja sad nebih prekucavao rjesenja evo ti link ka knjizi Dinamickog programiranja (na srpskom, Milana Vugdelije) u kojoj ces naci objasnjenje i algoritam za slican problem, to je Najduzi zajednicki podniz ali ako ga malo editujes smozes dobiti ono sto trazis, jer ti bi trebao to najbolje da znas, da mi nebi morali da odgonetavamo sto si ti mislio reci u objasnjenju zadatka najbolje je da ti to sam uradis. Pa evo link (mogao si koristiti pretrazivanje):
Cujte, taj zadatak je s hrvatskog državnog takmičenja i izgubio sam 4 sata na njemu da ga riješim, naravno bezuspješno. Zato sam vas i molio za pomoć iako mi nije baš dobro krenulo s svim tim lapsusima. 100% sam uvjeren da za nizove od po 1000 članova samo dinamičko programiranje može dati odgovor u roku od 5 sekundi, zato otpada i backtracking i brute-force i ne znam koje još metode.
Puno hvala na knjizi, možda mi bude sad lakše odgonetnuti rješenje.
Re: dinamički problem
Re: dinamički problem