Subset Sum

[•tarzanRo]

Am si eu urmatoarea problema. Am M*S - o suma de bani, un numar de N tipuri de monede, din fiecare tip de moneda avand un anumit numar de monede. Trebuie sa verific, daca cu banii pe care-i am, pot acoperi cea M*S suma de bani, astfel incat aceasta suma sa fie formata dintr-un numar M de subsume egale S. Daca se poate, atunci trebuie sa si spun cum se poate face acest lucru. Pot fi si mai multe solutii, trebuie doar sa arat una.
Ma poate ajuta si pe mine cu idei despre rezolvarea eficienta a acestei probleme?
Multumesc anticipat:)

ex. de date de intrare:
M * S = 80
tipuri de monede  : 10, 9, 8, 7, 6, 3, 2
numar de monede :  1, 1, 2, 2, 3, 3, 1

rezultat:

Se poate, astfel: 5 subsume de valoare 16 fiecare, astfel:( tipurile de monede)
10 6
9 7
8 2 6
8 2 6
7 3 3 3

[•alexandru92]

mi se pare ca poti   cu   backtraking ,daca ai gaisit  o solutie  valida  pui  "Da se poate" si apoi eixt(0); si ai terminat ..........daca nu se poate  dupa ce se executa  algoritmul back pui  "Nu se poate".    poti da si un exemplu ?
[later] dap  eu zic ca e back

[•tarzanRo]

Cred ca e totusi ceva mai bun decat atat, ceva in genul problemei "subset sum" am gasit pe net, dar nu prea stiu cum sa implementez...