Zadatak - Dinamicko programiranje

[2paca.zwaka]

Potrebno je organizovati izlet za celu skolu.Na izlet ide N ucenika koje treba raspodeliti u autobuse.Postoje dva tipa autobusa:
veci (kapacitet A, cena X);
manji (kapacitet B,cena Y);
Napisati program koji odredjuje koliko vecih i koliko manjih autobusa je potrebno da preveze sve ucenike a da se potrosi sto manje novca.
Ulaz :
broj ucenika N ---- 1<=N<=3000
kapacitet velikog busa A ---- 1<=A<=100
kapacitet malog busa B ---- 1<=B<=100
cena velikog busa X ---- 1<=X<=5000
cena malog busa Y ---- 1<=Y<=3000

Izlaz:
Prirodan broj C - najmanja ukupna cena izleta

Primer :
In:
100
40
30
1000
700


Out:
2400



E ovaj sam zadatak ja uradio i radi za 40% test primera medjutim dalje me obara vremenski limit.......pa sam skontao da se ovo moze odraditi dinamickim programiranjem......e da znam to uradio bih nesto pa bih i postavio ovde ali posto nzm nista o tome trazim samo pomoc da mi neko ovo odradi jednostavno da bih mogao da shvatim koncept dinam. prog........hvala puno

 

[bequick]

Postavi kod da vidimo

 

[2paca.zwaka]

Pa nisam radio nista sto se tice dinamickog resavanja ovog problema .....zato i trazim pomoc

 

[bequick]

Pa iskreno ja neznam ni sta se podrazumeva pod "dinamickim programiranjem", dinamicka alokacija memorije ili nesto trece?Ako je ovo prvo ne vidim kako ce ti ubrzati algoritam okaci ovaj kod koj si sad uradio pa verovatno moze da se optimizuje da jede toliko procesor.

 

[2paca.zwaka]

Optimizacija koda na odredjene nacine daj ne moram tebi govoriti da imas google

 

[bud@]

Tebi je potrebno koliko je moguc'e imati manjih autobusa za 3000 djaka jer su jeftiniji, pretpostavljam?
Zbunjuje me shto si naveo da je kapacited isti -> 100

 

[programmer^]

Evo ti link na kome imas uvod u dinamicko i neke najpoznatije probleme, sve objasnjeno

http://www.dms.rs/competitions/informatics/problems/sio_2009/Uvod u dinamicko programiranje.pdf

A kad uradim zadatak poslacu

 

[2paca.zwaka]

Hvala velika.....ovo sam vec citao......medjutim probleme ovde znam kasnije da resim donekle ali nzm na nekom novom problemu da primenim isto......to mi je najveci problem......verovatno ne shvatam toliko ideju uopste :/

 

[2paca.zwaka]

Tebi je potrebno koliko je moguc'e imati manjih autobusa za 3000 djaka jer su jeftiniji, pretpostavljam?
Zbunjuje me shto si naveo da je kapacited isti -> 100

Pa ne bas nego treba naci optimalno rjesenje koristeci male i velike busove xD
Jer mozes imat 100 ucenika
veliki bus moze 99 i kosta 1$ a mali moze 1 i kosta 10$......nzm optimalno, najjeftinije resenje

 

[programmer^]

Mozes da radis ovako:
da gledas da li je bolje da uzmes jedan skuplji ili za te pare da uzmes vise jeftinijih u zavisnosti od toga kako ces vise da prevezes. Tako ces da dodajes ono sto ti vise odgovara samo treba da pogledas poslednji put kad uzimas sta ti je bolje. Jer moze da se desi da si ti do sada uzimao ove velike, a sad mozes da uzmes manje ovih manjih za manje pare. Nadam se da si razumeo sta sam hteo da kazem, ako nisi ti reci pa cu pokusati malo bolje da objasnim