Algoritm Coin Changing

[•abc85]

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.

[•Cosmin]

De ce am impresia ca e tema?

[•abc85]

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.

[•devilkind]

din moment ce nu e tema si numai o chestie care vrei tu sa o inveti de dragul informaticii iti voi da numai ideea unei dinamici (nu stiu daca intra in timp si memorie din moment ce tu nu ai zis nici o restrictie).

Calculezi matricea A[ i ][ j ][ k ] - costul minim sa alegi j elemente din primele i si suma lor sa fie k.

Recurenta te las sa o deduci singur.

[•Cosmin]

abc ia vezi threadul asta http://infoarena.ro/forum/index.php?topic=2304.0

Cand vii pe site si la primul post intrebi o problema, e un semn de intrebare pt ca de obicei oamenii de pe site se apuca si fac probleme din arhiva nu vin cu probleme noi. De asemenea solutia pentru problema ta era foarte apropiata de algoritmii pe care ziceai ca i-ai studiat, si asta se intampla daca inveti ceva la scoala si apoi ca tema ti se da sa aplici pe o problema asemanatoare. E destul de enervant sa pui energie si sa raspunzi frumos la o intrebare pentru ca dupa aia sa aflii ca tocmai ai dezvaluit rezolvarea unui concurs in desfasurare sau ca l-ai ajutat pe cineva sa isi faca tema. Temele sunt facute nu pentru a lua informatia mura in gura ci pentru a incerca variatii a ceea ce ai facut la clasa.

Vroiam sa mai zic ca intrebarea ai pus-o intr-un mod destul de bun explicand frumos ce ai mai incercat inainte.