O problema

[•bogdan2412]

Poate cineva sa ma ajute la urmatoarea problema: Se da un sir de n numere. Sa se partitioneze sirul in doua subsiruri astfel incat suma elementelor din cele doua subsiruri sa fie cat mai apropiate.

[VladS]

Problema seamana cu Timus 1004 (parca) : "Pile of Stones".
Daca lungimea sirului este mica se poate face prin backtracking. Se face suma pe tot sirul, se gaseste submultimea cu suma cea mai apropiata de jumatate.

Problema parca s-a dat si la bursele Agora anul trecut la runda 25 sau 26. Se chema "Fotbal". Poti sa te uiti si pe solutia oficiala de acolo.

[•greco]

"O prima idee de rezolvare ar fi generarea tuturor submultimilor de cadouri, calcularea sumelor acestora si determinarea celei mai apropiate de jumatatea sumei totale a valorilor cadourilor. Dar aceasta varianta are o complexitate exponentiala, deci metoda este ineficienta.

O alta idee de rezolvare este construirea unui vector, astfel:
-presupunem ca n este numarul total de cadouri si Cadou[] este un vector care contine valorile cadourilor;
-S[0] = 0;
-S[j] = i, pentru i apartine {1, ..., n}, inseamna ca ultima valoare adaugata pentru a obtine un total j este Cadou;
-S[j]=n+1, daca subtotalul nu poate fi obtinut.

In variabila suma se va calcula suma totala a valorii cadourilor. Fie Cadou[] un tablou cu valorile tuturor cadourilor; atunci cadoul i va fi adaugat la subtotalul lui j pentru a obtine o noua valoare j+ Cadou. S[j]<i (un cadou nu poate fi adaugat la subtotal decat cel mult o data si vom adauga cadourile in ordine crescatoare). Ne intereseaza sa gasim cea mai apropiata valoare de mijloc, aceasta va fi una dintre sume."

Doina Hrinciuc - Logofatu - "Probleme rezolvate si algoritmi"

[•greco]

Da la Timus poti sa faci back.  

[•bogdan2412]

Mersi. Mi-am dat deja seama cum se facea.

[•Vman]

interesant, shi cand te gandesti k problema inca e valabila la .campion :lol:

[•Cosmin]

v-a placut fotbal de la ginfo?

[•vladcyb1]

Faceti voi back pt n=20000.    Nu mai cereti mey solutii la .campion in timpul rundei. Asa am incercat si yo la o runda, si am luat 0 pe un algoritm aprope perfect (citirea era gresita). Deci poarta ghinion.

[•bogdan2412]

Scuzati-ma. Cand am facut acel post nu shtiam ca e la campion. Am gasit-o altundeva. De problemele de la campion m-am apucat mai tarziu (in timpul saptamanii eram foarte ocupat sa invat pt teste la scoala)
Mersi pt ajutor.