N tipuri de monede

ENUNT: Avand la dispozitie n saculeti cu monede S1, S2, .... Sn, fiecare saculet Si continand Nri monede de valoare Vi sa se afiseze toate modalitatil de a plati o suma data S folosind numai monezi din saculeti.

EXEMPLU: Pentru n=3 , Nr=(10,2,5), V=(1,2,5) si S=5 programul va genera

5 * 1 leu

3 * 1 leu + 1 * 2 lei

1 * 1 leu + 2 * 2 lei

1 * 5 lei

SOLUTIE:

• Solutia x[1]......x[n]. Elementul x[i] va avea ca valoare numarul de monede care s-au folosit din saculetul i

• x[k] poate avea ca valoare orice valoare din intervalul [0,Nrk].

• Valid

  1. daca k<n --> suma platita pana la acel moment sa nu depaseasca S

  2. daca k=n --> suma platita sa fie egala cu S

PROGRAM C++:

#include <iostream>

using namespace std;

char sp5[]=" ";

int x5[20], n5, nrsol5=0, nr[20], val[20], sum[20], S;

int Valid5(int k)

{ sum[k]=sum[k-1]+val[k]*x5[k];

if (sum[k]>S) return 0;

if (k==n5 && sum[k]!=S) return 0;

return 1;

}

void Afisare5()

{ int i,j;

cout<<sp5;

for(i=1;i<=n5;i++)

if (x5[i]!=0) cout<<x5[i]<<"*"<<val[i]<<" lei + ";

cout<<endl;

nrsol5++;

}

void Back5()

{ int k=1, cand;

x5[1]=-1;

while (k>0)

{ cand=0;

while (cand==0 && x5[k]<nr[k])

{ x5[k]++;

cand=Valid5(k);

}

if (cand==0) k--;

else if (k==n5) Afisare5();

else {k=k+1; x5[k]=-1;}

}

}

int main()

{ int i;

cout<<endl<<endl<<sp5<<"Plata unei sume de bani"<<endl;

cout<<endl<<sp5<<" Numarul tipuri monezi: "; cin>>n5;

cout<<sp5<<" Dati suma de plata: "; cin>>S;

cout<<endl;

for (i=1;i<=n5;i++)

{ cout<<sp5<<" Valoare moneda tip "<<i<<": "; cin>>val[i];

cout<<sp5<<" Numar monezi tip "<<i<<" : "; cin>>nr[i];

}

cout<<endl<<"Solutiile sunt: "<<endl;

Back5();

cout<<endl<<sp5<<"Numar solutii: "<<nrsol5;

return 0;

}