dinamički problem

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 ???

Potpis

CHUPCKO

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?

Rajko

Rajko, u pitanju je podniz, a njegovi elementi ne moraju biti uzastopni clanovi odgovarajuceg niza. Uostalom, pogledaj pod Subsequences:
http://www.maths.lse.ac.uk/Courses/MA203/sec1a.pdf

A sto se resenja tice, ne vidim kako bi se moglo naci "dinamicki" - pre ce biti da je gruba sila u pitanju.

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

Rajko

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):

http://www.devbase.net/knjige/Dinamicko%20programiranje.pdf

Potpis

Njutn laze! Lake padaju brze...

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.

Nema na cemu. Samo jel imas ti sajt sa tim zadacima i stranicu hrvatskog tima koji priprema takmicenja?

Potpis

Njutn laze! Lake padaju brze...

Tim nema stranicu (koliko znam), ali na službenoj stranici saveza public.srce.hr/hsin imaš te a i hrpu starih zadataka. Uživaj.

Hvala na linku.

Potpis

Njutn laze! Lake padaju brze...