Monede: combinații sau ordini diferite în C++

Câte moduri avem de a forma o sumă folosind monede cu valori date? Întrebarea este incompletă până stabilim dacă ordinea contează. Pentru suma 3 și valorile 1,2, combinațiile sunt 1+1+1 și 1+2. Dacă ordinea contează, apare separat și 2+1.

Vom rezolva ambele cerințe. Diferența se vede în ordinea buclelor, dar explicația vine din semnificația stării. Nu schimba două bucle doar fiindcă un exemplu mic pare să funcționeze: poți calcula corect răspunsul unei alte probleme.

Cum funcționează

Pentru combinații, după prelucrarea primelor i tipuri, d[x] numără reprezentările sumei x folosind numai aceste tipuri. Inițial d[0]=1 și celelalte valori sunt zero. Există o singură combinație vidă; o sumă pozitivă nu poate fi construită fără niciun tip de monedă.

Când introducem moneda c, păstrăm în d[x] combinațiile care nu o folosesc și adăugăm d[x-c], pentru cele care o folosesc cel puțin o dată. Sumele se parcurg crescător: d[x-c] poate conține deja moneda curentă, fiindcă disponibilitatea este nelimitată. Nu este o eroare de reutilizare, ci exact condiția problemei.

Tipurile se prelucrează într-o ordine fixă. Fiecare combinație este identificată prin numărul de monede din fiecare tip, nu printr-o ordine a alegerilor. Astfel, 1+3 și 3+1 nu sunt numărate separat. Valorile trebuie să fie distincte; două intrări egale ar fi tratate ca tipuri diferite și ar produce supranumărare.

Pentru secvențe ordonate, d[x] numără toate șirurile de monede cu sumă x. Parcurgem întâi suma și alegem ultima monedă. Pentru fiecare c<=x adunăm d[x-c]. Acum șirurile care se termină în valori diferite sunt familii separate, iar ordinea monedelor este păstrată în numărare.

Ambele programe citesc n și S, apoi n valori distincte: 1<=n<=20, 0<=S<=1000 și 1<=c[i]<=1000. Afișează răspunsul modulo 1000000007, nu numărul exact atunci când acesta depășește modulul. Aplicăm modulo după fiecare adunare; valorile intermediare sunt stocate în long long.

Capacitățile clasice sunt 20 pentru c și 1001 pentru d. Mărimile logice sunt n și S+1, iar indicii sunt de la zero. Variantele std::vector alocă exact aceste mărimi. Nu schimbăm formulele, bazele sau limitele admise; includem doar antetul vector și înlocuim declarațiile.

Exemplu urmărit pas cu pas

Pentru valorile 1,2,3 și suma 4, urmărim combinațiile:

tipuri permise     d[0] d[1] d[2] d[3] d[4]
niciunul            1    0    0    0    0
1                   1    1    1    1    1
1,2                 1    1    2    2    3
1,2,3               1    1    2    3    4

Cele patru combinații sunt 1+1+1+1, 1+1+2, 2+2 și 1+3. Cu ordine, 1+1+2 are trei permutări, iar 1+3 are două. Totalul devine 1+3+1+2=7. Un tabel cu aceeași dimensiune poate avea o semnificație complet diferită.

Implementare C++17

Combinații, fără ordine

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, s;
    std::cin >> n >> s;
    int c[20];
    long long d[1001] = {};
    const long long MOD = 1000000007;
    for (int i = 0; i < n; ++i)
        std::cin >> c[i];
    d[0] = 1;
    for (int i = 0; i < n; ++i)
        for (int x = c[i]; x <= s; ++x)
            d[x] = (d[x] + d[x - c[i]]) % MOD;
    std::cout << d[s] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, s;
    std::cin >> n >> s;
    std::vector<int> c(n);
    std::vector<long long> d(s + 1, 0);
    const long long MOD = 1000000007;
    for (int i = 0; i < n; ++i)
        std::cin >> c[i];
    d[0] = 1;
    for (int i = 0; i < n; ++i)
        for (int x = c[i]; x <= s; ++x)
            d[x] = (d[x] + d[x - c[i]]) % MOD;
    std::cout << d[s] << '\n';
}

Secvențe, cu ordine

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, s;
    std::cin >> n >> s;
    int c[20];
    long long d[1001] = {};
    const long long MOD = 1000000007;
    for (int i = 0; i < n; ++i)
        std::cin >> c[i];
    d[0] = 1;
    for (int x = 1; x <= s; ++x)
        for (int i = 0; i < n; ++i)
            if (c[i] <= x)
                d[x] = (d[x] + d[x - c[i]]) % MOD;
    std::cout << d[s] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, s;
    std::cin >> n >> s;
    std::vector<int> c(n);
    std::vector<long long> d(s + 1, 0);
    const long long MOD = 1000000007;
    for (int i = 0; i < n; ++i)
        std::cin >> c[i];
    d[0] = 1;
    for (int x = 1; x <= s; ++x)
        for (int i = 0; i < n; ++i)
            if (c[i] <= x)
                d[x] = (d[x] + d[x - c[i]]) % MOD;
    std::cout << d[s] << '\n';
}

De ce funcționează și cât costă

La combinații, separăm după folosirea tipului curent. Eliminarea unei monede curente identifică unic o combinație de sumă x-c care folosește tipurile deja introduse. La secvențe, separăm după ultima monedă. În ambele cazuri, partiționarea justifică adunarea fără omisiuni sau dubluri.

Ambele implementări au O(n*S) timp și O(n+S) memorie. Complexitatea identică nu înseamnă că rezultatele trebuie să fie identice; obiectele numărate diferă.

Greșeli frecvente

Nu folosi valori de monede egale ca tipuri distincte fără să fie cerut. Nu seta d[0]=0. Nu parcurge descrescător sumele dacă fiecare tip poate fi folosit nelimitat: ai ajunge la o variantă în care tipul curent este folosit cel mult o dată.

Exersează

Cu valorile 1 și 2, află răspunsurile pentru suma 4 în ambele interpretări. Explică și cazul S=0.

Rezolvare explicată: Fără ordine există trei combinații: patru monede de unu, două de unu și una de doi, respectiv două de doi. Cu ordine sunt cinci șiruri. Pentru suma zero, ambele variante numără exact reprezentarea vidă, deci răspunsul este unu.

Probleme de practică

Rezolvă cele trei probleme în ordinea de mai jos. Deschide fiecare problemă, scrie soluția și verific-o folosind testele locale din pagină. Respectă formatul de intrare, limitele și ieșirea cerută; acestea pot diferi de programul din lecție. Trimiterea pentru punctaj necesită autentificare și un evaluator activ.

1. Plata în mai multe moduri. Numără combinațiile de monede fără a distinge ordinea lor. Adaptează dimensiunile și folosește modulul din enunț, inclusiv pentru suma zero.

2. Sume ordonate cu termen limitat. Compară cu problema precedentă: aici ordinea termenilor contează. Explică de ce schimbi ordinea buclelor și de ce rezultatul se afișează exact, fără modulo.

3. Partiții cu termen cel mult k. Extensie de modelare: privește părțile 1..k ca valori de monede. Reordonarea acelorași părți nu produce o partiție nouă.

Continuă să înveți

Înapoi la programarea dinamică. Recapitulează tablourile și recursivitatea.

Întrebări frecvente

Trebuie sortate monedele?

Nu. Pentru combinații este suficient ca fiecare tip distinct să fie introdus o singură dată, într-o ordine fixă. Sortarea poate ajuta lectura, dar nu schimbă rezultatul.

De ce d[0] este unu?

Reprezentarea vidă este un obiect valid de numărat. Ea permite ca o singură monedă de valoare x să contribuie la d[x].

De ce rezultatele sunt date modulo?

Numărul reprezentărilor poate crește foarte mult. Cerința programelor definește explicit restul împărțirii la 1000000007, iar adunarea respectă acest calcul.

Ce schimb dacă am o singură monedă din fiecare tip?

Pentru numărarea submulțimilor, introduci tipurile pe rând și parcurgi sumele descrescător. Astfel, d[x-c] nu folosește încă moneda curentă.

Cum verific că nu număr dubluri?

Pentru o sumă mică, enumeră reprezentările și stabilește ce face două reprezentări egale. Compară separat numărul combinațiilor și numărul șirurilor ordonate.