[es] - [zadatak] sume nesusednih

steki96
Srbija

Član broj: 320350
Poruke: 2
*.dynamic.isp.telekom.rs.

Profil

^{09.01.2014. u 17:24 - pre 137 meseci}

Moze neko da mi da mi resi zadatak maksimalne sume nesusednih u nizu ,po mogucstvu i da obijasi ideju ili samo da da ideju...u pitanju je dinamicko programiranje(kod u c++) i KOJA JE FORA SA OVIM ZADACIMA

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3570

Jabber: djoka_l

+1527 Profil

Re: [zadatak] sume nesusednih

^{09.01.2014. u 22:01 - pre 137 meseci}

Mogao si malo bolje da objasniš, ali evo kako sam ja shvatio.
Recimo da imaš niz od 5 elemenata {1,2,3,4,5}.
Susedni od 1 je 2,
susedni od 2 su 1 i 3,
susedni od 3 su 2 i 4,
susedni od 4 je 5 i
susedni od 5 je 4

treba naći
max(
sumnesusednih( {}, 1, {3,4,5}),
sumnesusednih( {}, 2, {4,5}),
sumnesusednih( {1}, 3, {5}),
sumnesusednih( {1,2}, 4, {}),
sumnesusednih( {1,2,3}, 5, {})
)

Dakle sumnesusednih ima 3 parametra, levi niz nesusednih elemata, centrali element i desni niz nesusednih elemenata, s tim da neki od ovih nizova može biti prazan.
Ukoliko niz nije prazan, on nadalje treba da da sve kombinacije nesusednih.
Pogledaj poslednji poziv f-je

sumnesusednih( {1,2,3}, 5, {})

ovo dalje treba da se radi kao
retrun 5+max(
sumnesusednih({}, 1, {3}),
sumnesusednih({}, 2, {}),
sumnesusednih({1}, 3, {})
)
prvi sum treba da vrati 1+3, drugi 2, treći 1+3
pa je onda max=9 za elemente 1,3,5

Ovo je ideja, a ti to pretvori u c++ kod.

Odgovor na temu