Modalitățile de obținere a unei sume

Ce reprezintă o soluție

O modalitate de plată este stabilită de numărul de bancnote luate din fiecare cupiură, iar acest număr se reține în tabloul b: b[i] arată câte bancnote de cupiura c[i] intră în plată. O soluție este deci un tablou b cu proprietatea

b[1]·c[1] + b[2]·c[2] + … + b[n]·c[n] = s.

Ordinea în care sunt înmânate bancnotele nu are importanță, iar tabloul b o elimină: pentru fiecare cupiură se reține numai câte bancnote se folosesc, nu și în ce moment. Plata sumei de 10 lei cu o bancnotă de 5 lei, una de 3 lei și una de 2 lei dă același tablou b, indiferent de ordinea în care sunt numărate bancnotele, deci este o singură soluție.

Cupiurile care nu se folosesc au b[i] = 0 și nu apar la afișare. De aceea în exemplul din enunț, la b=(3,1,0,1), cupiura de 3 lei lipsește din rezultat.

Descrierea algoritmului în limbaj natural

Soluțiile se generează prin backtracking: cupiurile se iau pe rând, iar pentru fiecare se stabilește numărul de bancnote folosite. Se pornește de la prima cupiură, cu suma întreagă rămasă de plătit.

Pentru cupiura i se încearcă, pe rând, toate numerele de bancnote care nu depășesc suma rămasă: de la 0 până la cel mai mare k pentru care k·c[i] este cel mult egal cu această sumă. Pentru fiecare valoare încercată se reține b[i] = k, se scade k·c[i] din suma rămasă și se trece la cupiura următoare.

Când toate cupiurile au fost parcurse, adică s-a depășit cupiura cu numărul n, se verifică suma rămasă: dacă este 0, tabloul b conține o modalitate validă de plată și se apelează subprogramul tipar, care o afișează; dacă nu este 0, plata nu s-a încheiat și se revine, fără să se afișeze nimic.

Revenirea se realizează prin întoarcerea din apelul recursiv: după ce s-au încercat toate valorile posibile pentru cupiura i, controlul se întoarce la cupiura i−1, unde se trece la valoarea următoare.

Zeroul este inclus printre valorile încercate, fiindcă enunțul nu cere ca toate cupiurile să fie folosite; el este chiar cazul în care o cupiură nu contribuie la sumă.

Programul

#include <iostream>
using namespace std;

/* Variabilele cerute de enunt sunt globale: subprogramul tipar nu are
   parametri si lucreaza direct cu ele. */
int n, s;
int c[11];   // cupiurile din casierie
int b[11];   // cate bancnote se folosesc din fiecare cupiura

/* Afiseaza modalitatea de plata aflata in tabloul b, in formatul cerut:
   numai cupiurile folosite efectiv, iar cuvantul "leu" doar pentru cupiura
   de 1 leu. */
void tipar() {
    for (int i = 1; i <= n; i++)
        if (b[i] > 0) {
            cout << b[i] << "x" << c[i];
            if (c[i] == 1)
                cout << "leu ";
            else
                cout << "lei ";
        }
    cout << endl;
}

/* Incearca, pentru cupiura i, toate numerele de bancnote care incap in suma
   ramasa de platit. */
void construieste(int i, int ramas) {
    if (i > n) {
        if (ramas == 0)
            tipar();
        return;
    }

    for (int k = 0; k * c[i] <= ramas; k++) {
        b[i] = k;
        construieste(i + 1, ramas - k * c[i]);
    }
}

int main() {
    cin >> s >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    construieste(1, s);

    return 0;
}