Suma maxima

Am si eu o problema careia nu sunt sigur ca i-am inteles 100% cerinta:

Se dau n(n+1)/2 numere naturale aranjate intr-un triunghi format din elementele de sub si de pe diagonala unei matrici patratice de ordin n.
Se calculeaza sume pornind din elementul de pe prima linie prin deplasari in vecinii de sub si din dreapta. Gasiti suma maxima care se poate calcula astfel si care sunt valorile din care se obtine suma maxima

Exemplu:
n=4
2
3 5
6 3 4
5 6 1 4
suma maxima este 17
si se obtine din valorile {2, 3, 6, 6}

Nu vreau sa imi faceti problema/programul, vreau doar sa imi explicati exemplul in detaliu (cum de a trecut prin 2,3,6,6 incat sa faca suma 17). Multumesc

pornesti de la 2, unde "te deplasezi" ?

MarianG, on 16 aprilie 2019 - 20:47, said:

Da, pornesti de la [0,0], apoi te deplasezi fie in dreapta fie in jos si vezi care dintre ele are valoare maxima ca sa o adaugi la suma

pornesti de la [0,0] -- care e urmatorul si singurul tau pas ?

Urmatorul pas (fiind si singurul posibil) e catre [1,1], adica 3.

doar asa, dar e gresit enuntul

Quote

Edited by MarianG, 16 April 2019 - 21:19.

este o problema clasica de programare dinamica

le: "vecinii de sub si din dreapta" se refera de fapt la elementele de pe linia urmatoare, fix in jos sau in jos-dreapta, nu la deplasari pe aceeasi linie.

Edited by _Smiley_, 16 April 2019 - 21:22.

Nu mi se pare neaparat gresit anuntul, mai degraba e un pic "obfuscat" .
Cerinta s-ar putea traduce in "alege un numar de pe fiecare linie, tinand cont ca daca ai ales elementul X[i,j], urmatorul element ales Y[i+1,k] trebuie sa aiba k>=j (i fiind indexul liniei iar j si k indecsii de coloane).

E o problema de programare dinamica asa cum spunea cineva mai inainte. Se folosesc 3 matrici, in una memorezi triunghiul de numere, in alta pastrezi sumele maxime ce se pot forma pornind de la fiecare element si in a treia pastrezi drumul.
Matricea initiala e

2 0 0 0
3 5 0 0
6 3 4 0
5 6 1 4

Formezi matricea cu sumele maxime. Asta se face plecand de la ultima linie a matricii initiale. Practic suma maxima ce poate fi formata pornind de la un element al ultimei linii e acel element pentru ca de aici nu mai ai unde avansa. Apoi, pentru liniile anterioare ultimei vezi pentru elementul din matricea initiala, unde e mai bine sa mergi, in jos sau jos-dreapta. Pentru a vedea asta aduni elementul a[i][j] din prima matrice, pe rand cu elementul b[i+1][j] din a doua matrice si cu elementul b[i+1][j+1]. Vezi care dintre valori e mai mare si aceea o pastrezi in b[i][j]. Deasemenea, pentru a vedea si drumul ce trebuie parcurs in matricea a pentru a obtine suma maxima, folosesti matricea c in care stochezi pe pozitia c[i][j],  j trebuie sa mergi in jos sau j+1 daca ati mers in jos-dreapta.
Se obtin astfel matricele:

A            B                 C
2 0 0 0     17  0  0 0        1 0 0 0
3 5 0 0     15 14  0 0        1 2 0 0
6 3 4 0     12  9  8 0        2 2 4 0
5 6 1 4      5  6  1 4        0 0 0 0

Deci suma maxima pornind din a[1][1] este ca din b[1][1],deci 17. Cum o obtii? Pai pleci din a[1][1] deci au 2+. Te uiti ce ai la c[1][1], e un 1 acolo, asa ca pe urmatoarea linie(2) iau elementul cu i=2 si j=1 (pentru ca c[1][1] e 1). Deci am pana aici 2+3 si tot asa pana ajung la ultima linie si am suma 2+3+6+6.

Sper sa ma fi facut inteles, daca nu cauta programare dinamica pe google si gasesti problema pe acolo. E celebra.

Edited by sharp10, 19 April 2019 - 19:44.

de ce 3 matrici ?
ai o harta si un numar determinabil de trasee,

pornesti din varf, si ai doua obtiuni pentru fiecare nod: la stanga (0) sau la dreapta (1),
in acest fel ai 2^n-1 drumuri, in cazul prezentat 2³
primul caz, strict stanga, 000₂ = 0 | suma[0] = 2 + (3+6+5) = ...
al doilea caz, 001₂ = 1 | suma[1] = 2 + (3+6+6) = ...
al treilea caz, 010₂ = 2 | suma[2] = 2 + (3+3+6) = ...
...
ultimul caz, strict dreapta,
111₂= 7  | suma[7] = 2 + (5+4+4)

Edited by MarianG, 20 April 2019 - 17:32.

nu ai neaparat nevoie de 3 matrici, te poti descurca si cu 2(dupa ce procesezi o pozitie, nu mai ai nevoie de valoarea ei ci doar de maximul sumei pe care o poti obtine ajungand in acea pozitie). ba chiar si cu o singura matrice (avand in vedere ca "harta" initiala foloseste e un triunghi, deci foloseste doar jumatate dintr-o matrice).

dar daca sugerezi backtracking in loc de programare dinamica, atunci ar trebui sa te uiti un pic pe la performanta. cu BT performanta e cea mai scazuta.

ps: este "optiuni", nu "obtiuni".

Cum arata asta pas cu pas?

a detaliat sharp10 mai sus.