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
daca k<n --> suma platita pana la acel moment sa nu depaseasca S
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;
}