Mala Zrinka slavi rodjendan i prijatelji joj dolaze na parti. Ona zeli svakom prijatelju dat nekoliko bombona, ali tako da oni najpametniji dobe najvise :). Napravila je robot koji moze ici samo u smjeru jug ili zapad (gornji lijevi kut je na sjevero-istoku) na i stavila ga na neku plocu dimenzija NxM podjeljena u kvadratice 1x1 tako da se na svakom kvadraticu nalazi odredjeni broj bombona. Svaki prijatelj mora odvoziti robot od pozicije (1,1) do pozicije (N,M). Robot skupi sve bombone s kvadratica kojima putuje. I ti dolazis na parti i jako volis bombone pa te zanima koliko ih mozes najvise skupit.

U prvom redu dva prirodna broja N <= 100 i M <= 100, dimenzije ploce.

U sljedecih N redova nalazi se M prirodnih brojeva (ili nula) manjih od 1000 (broj bombona)

U prvom i jedinom redu treba ispisati koliko mozes skupiti bombona.

Pomoć molim :)

Zadatak mozemo rijesiti primjenom klasicnog dinamickog programiranja.

dakle imamo array dp[ MAX_ROW ][ MAX_COL ];

dp[i][j] - oznacava maximalan broj bombona do pozicije i, j.

za svaku poziciju izracunamo :

dp[i][j] = max( dp[i-1][j], dp[i][j-1] ) + A[i][j]; // A - broj bombona na i,j pos.

moramo paziti samo na granicne slucajeve za i == 1 || j == 1

rjesenje je dp[N][M];

HINT : Zadatak je moguce rijesiti vec pri ucitavanju.

Ok,hvala,napisao kod i radi :D.
E sad..to je dinamicko programiranje? Sto je to zapravo :p? Na cemu se temelji?

Dinamicko programiranje, hmm. Iako je poprilicno jednostavna ideja, tesko je objsniti sto je to zapravo.

Dinamicko programiranje, bio bi sistem razbijanja velikog problema na manje te potom rjesavanjem manjih, rijesiti veliki.

Dinamicko programiranje je razmjena, prostor za vrijeme. Tj. sve manje probleme koje izracunas, spremis tako da ih nemoras ponovno izracunat.

Napr, fibbonacijevi brojevi, ukoliko bi ih rjesavali rekurzivno.

fibo( 5 ) -> racunam fib(4) fib(3)

fib( 4 ) -> fib(3) fib(2)

...

kao sto vidmo u drugome redu, drugi puta racunam fib(3). Pa ako ga prvi puta spremim onda ga drugi puta samo vratim.

Ako se problem rjesava rekurzivno, tada se koristi memoizacija(spremanje).

No vijek je bolji bottom_up ako je moguc.

Mogao bi pisati jos satima, ali najbolje da pogledas ove zadatke, pa javis sto ti nije jasno.

Sto se tice naseg primjera :

U nizu dp, mi imamo rjesenja za sve pozicije, ne samo [N][M].

Dake dp[i][j] = max( dp[i][j-1], dp[i-1][j] ) + A[i][j], mi uzimamo bolje rjesenje između 2 postojeca.

Gledamo, jeli bolje doci do (i,j-1) pa skrenuti desno ili je bolje doci do (i-1, j) pa skrenuti dolje.

Dakle u nizu dp imamo spremljena SVA rjesenja od pozicije (1, 1).

Ovdje su klasicni primjeri.

http://forum.zrs.hr/index.php/topic,289.0.html

Hvala puno na linku :D!

Moj problem u ovom zadatku je bio što sam razmišljao da li je bolje s polja (x,y) ići na (x+1,y) ili (x,y+1),a tako ga je nemoguće rješit :/(trebao bi gledat sve kombinacije )

A dp moram proučit vjerojatno če zatrebat sad na županijskom

Razred, skola, grad ?

2.,MIOC,Zagreb

Prouci zadatak BOND, HONI 1.kolo 2006/2007. Veoma cesto bude, takav nekakav sablonski zadatak. I prosle i ove godine je bio(II podskupina).

Rjesio prva 4 iz tog kola u 20min :D.Na ovom sam zapeo al nemoj rjesenje govorit da promislim jos malo :p.

http://www.spoj.pl/problems/KNAPSACK/

Evo problem na kojem je razrađena ideja dinamickog p.

#include <cstdio>
#include <algorithm>
using namespace std;

struct stvar{
    int size;
    int value;
    double koef;
};

stvar stvari[2002];


bool cmp( const stvar &x , const stvar &y){
    if( x.koef < y.koef ) return 0;
    return 1;
     }

int main(){

    int S,N;

    scanf("%d %d",&S,&N);

    for(int i = 0 ; i < N ; ++i)
    scanf("%d %d",&stvari[i].size,&stvari[i].value);

    for(int i = 0 ; i < N ; ++i) stvari[i].koef = stvari[i].value/stvari[i].size;

    sort(stvari,stvari+N,cmp);
    int o = -1;
    int TOT = 0;

    while( S != 0 ){

    ++o;

    if( o == N ) break;

    if( stvari[o].size > S ) continue;

    S -= stvari[o].size;
    TOT += stvari[o].value;

    }

   printf("%d",TOT);

    return 0;
}

 Ovako sam ja...al neradi :/

Bi li ono gore radilo da sam jos jednom sortirao uzlazno,ali po stvar.size?(tj. Bolja je stvar 8 8 od stvari 9 9)

ma ne.ovo je totalno krivo XD

Nemozes primjenjivat greedy rješenje, ovaj primjer se mora rjesavati DP-om.

http://www.dir.hr/pripreme/1998_1999/dinamicko.html

Ovdje je relativno dobro objasnjeno. S time da ovdje nije 1-0 knapsack.

Imam pitanje..ponovo :D

recimo imamo matricu[R][S]...koja ima upisan ulaz 'U' i izlaz 'I'.

Optimalnu putanju izmedu pocetka i kraja dobili bi občnim bfsom.

No recimo da imamo više ulaza,a opet samo 1 izlaz...Kako bi sada dobili tu opt.putanju?

(recimo da je R i S masovan broj,pa je nemoguće pozivat bfs za svaki ulaz)

Prijatelj mi je pričao da se tu koristi priority_queue,neke strukture,al se ne sjećam detalja

Ne priority queue. Obicni Q na nacin da ubacis sve ulaze na pocetki.

for( int i = 0; i < R; ++i ) {

  scanf( "%s", mapa[i] );

  for( int j = 0; j < S; ++j ) {

    if( mapa[i][j] == 'U' ) {

      Q.push( make_pair(i, j) );

      p[i][j] = 0;

    }

  }

}

pa normalni bfs i dobit ces najkracu udaljenost izmedju svake tocke i

najblizeg ulaza. Mozda se moze sa PQ-om, ali ovo sigurno radi.

mhm.....Jel ideš na Honije redovito?

Ne , zasto ??

Mislio sam da ideš,jedan zadatak...VUK.Baš mi to tu treba,ne čini mi se da bi se tako mogao rješit :/

EDIT : evo link

taj zadatak sam ja rjesio na taj nacin.

jednim bfs-om sam nasao udaljenos izmedju svake tocko i najblizeg stabla, pa binarnim pretrazivanjem nasao optimalan put.

Inace taj zadak se moze rjesiti PQ-om, ma da je slozenost skoro ista jer ubacivanje u Q kosta .

Cek..napravio si bfs za vuk -> jazbina? i dobio si on matricu integera punu brojeva..sta si onda tocno radio

Nakon sto napravis matricu udaljenosto, napr dist[x][y].

napr

+..

..+

...

...

dist izgleda ovako

011

110

221

332

tada radis binarno pretrazivanje.

Ako mozes doci do jazbine s udaljenoscu 4 tada sigurno mozes i sa 3 , 2 ...

neka je doljnja granica 0, a gornja dist[ vukx ][ vuky ]

probas s mid = (donja + gornja) / 2

ako moze onda donja = min

else gornja = min - 1

to radi dok god je donja < gornja

kako probas, tako sto radis bfs od vuka do jazbine, a uvjet je da udaljenost mora biti veca ili jednaka onoj s kojom probas.

rjesenje je donja granica.

Shvaćam..Hvala

I kako je proslo zupanijsko... ako si bio

Ne pitaj....

Ti?

EDIT: rjesio prva 2.. 2 sata pokušao shvatit 3. zadatak koji nisam shvatio do kraja natjecanja i toeto :(

KAKO ROBOT KOJI SE GIBA U MATRICI DIMENZIJA 4 VISINE i 8 ŠIRINE MOŽE DOČI U POLJE (8,2) ???

Ma otkad ovaj DUMP priprema zadatke kvaliteta se srozala skroz. A ja nisam bio na ocjenjivanju, inace sam rjesio sva 4. pa bumo vidli. Zadnji zadatak II podskupine ima pre nizak time limit pa necu ima 100% na tom zadatku. A ostalo bi trebalo biti dobro.

Ajde,puno sreće :D

Ja sam tek sad skužio onaj razvoj softwarea...Na to ću vjerojatno ić sljedeće godine,baš me zanima to

Ja nisam ni pročitao 4.,Na 3. sam se davio ko stoka....što je najgore taj 4. bih možda i mogao rješiti,kolko tolko znam MST

Ma i to Microsoft organizira, ja sam imao projekt za linux, nisam se ni usudio ici.

Zasto?