exercitiu rezolvat Metoda Backtracking

Plata unei sume de bani

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 aplati 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:

   I. Solutia x[1]......x[n]. Elementul x[i] va avea ca valoare numarul
      de monede care s-au folosit din saculetul i
  II. x[k] poate avea ca valoare orice valoare din intervalul [0,Nrk].
 III. Valid
    - daca k<n --> suma platita pana la acel moment sa nu depaseasca S
    - daca k=n --> suma platita sa fie egala cu S

 Implementare

#include<iostream>
using namespace std;

char sp[]="   ";

int x[20], n, nrsol=0, nr[20], val[20], sum[20], S;


int Valid(int k)
{sum[k]=sum[k-1]+val[k]*x[k];
 if (sum[k]>S) return 0;
 if (k==n && sum[k]!=S) return 0;
 return 1;
}

void Afisare()
{int i,j;
 cout<<sp;
 for(i=1;i<=n;i++)
   if (x[i]!=0) cout<<x[i]<<"*"<<val[i]<<" lei + ";
 cout<<char(8)<<char(8)<<"   "<<endl;
 nrsol++;
 if (nrsol%22==0) cin.get();
}

void Back()
{int k=1, cand;
 x[1]=-1;
 while (k>0)
    {cand=0;
     while (cand==0 && x[k]<nr[k])
      {x[k]++;
       cand=Valid(k);
      }
     if (cand==0) k--;
     else if (k==n) Afisare();
          else {k=k+1; x[k]=-1;
               }
    }
}


int main()
{int i;
 cout<<endl<<endl<<sp<<"Plata unei sume de bani"<<endl;
 cout<<endl<<sp<<" Numarul tipuri monezi: "; cin>>n;
 cout<<sp<<" Dati suma de plata: "; cin>>S;
 cout<<endl;
 for (i=1;i<=n;i++)
    {cout<<sp<<" Valoare moneda tip "<<i<<": "; cin>>val[i];
     cout<<sp<<" Numar monezi tip "<<i<<"  : "; cin>>nr[i];
    }
 Back();
 cout<<endl<<sp<<"Numar solutii: "<<nrsol;
 return 0;
}