Cosmin,


In primul rand, multumesc pentru raspunsul prompt.

In al doilea rand, chiar daca este o tema, care este problema? Nu v-am cerut cod complet, ci doar o idee salvatoare. V-am rugat sa discutam pareri, sa imi deschideti putin orizonturile spre noi idei avand in vedere ca problema e de natura algoritmica si vad ca aici sunt multe persoane inclinate spre acest domeniu. V-am prezentat ceea ce am incercat eu sa fac pana acum de capul meu si unde m-am blocat. De aici cer ajutor unora mai mari ca mine pe partea asta. Nu am dat in cap, puteai pur si simplu sa ignori acest mesaj daca credeai asta. Dar banuiesc ca romanul e considerat mai intai hot si dupa aia prost -- nu e rau.

In al treilea rand, problema pe care o propun nu este pentru o tema. Banuiesc ca as fi vrut sa fie pentru o tema, nu m-as mai fi chinuit atata cu ea, cu atat mai mult nu as fi incercat sa conving un om care a facut atatea la viata lui -- banuiesc, si cu ajutorul altora -- sa imparteseasca mai departe din cunostintele lui in loc sa dea in cap.

O zi buna.

[elem = (1, 3, 5)]

Salut tuturor,

Scriu in speranta ca voi gasi un ajutor de la cineva mult mai experimentat in algoritmica decat mine. Problema imi da batai de cap de cateva zile si as vrea sa-i dau de cap cumva.

Problema mea vine cam asa: am un vector de elemente elem = (1, 3, 5)  si un cost asociat fiecarui element  cost = (52, 145, 251). Mai am o variabila total care este 6 sa zic. Pot sa iau orice combinatie de elemente (se pot si repeta) cu conditia ca la sfarsit, suma elementelor sa fie EXACT 6  (intotdeauna va exista cel putin o varianta ca asta). In caz ca sunt mai multe variante optime din punct de vedere al numarului de elemente (cat mai putin elemente folosite), vreau sa se ia varianta cu cost minim.

Din amintirile mele prafuite de algoritmica am redus problema la unul din doi algoritmi clasici dar care trebuie modificati cumva:
1) Prima incercare a mea a fost problema rucsacului (unbounded knapsack). Ar fi fost foarte buna, insa imi returneaza costul maxim, iar daca incerc sa-l schimb in minim nu mai obtin exact numarul dat de variabila total (adica 6 in cazul de fata)
2) A doua incercare a fost unul din algoritmii Coin Changing. Cum programarea dinamica nu mi-ar putea oferi decat unul din rezultatele optim din punct de vedere al numarului de elemente (si nu pot verifica si celelalte variante pentru cost minim cu algoritmul clasic -- poate stie altcineva o altfel de implementare?), am incercat algoritmul de aici http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html care imi numara toate variantele posibile de a scrie total ca suma de elemente insa nu reusesc sa-l modific pentru a-mi retine si solutiile efective.

Va multumesc anticipat si orice fel de comentariu este bine venit.

Vreau sa testez un program care foloseste ca input un graf orientat.

Am nevoie de o unealta care sa-mi genereze niste teste mari pentru 2000+ varfuri, cu tot cu costuri, iar graful obtinut sa fie cat de cat real si din orice varf sa se poata ajunge macar pe o cale la oricare alt varf.


Va multumesc anticipat.