Monede: număr minim și reconstruire în C++

Avem tipuri de monede cu valori întregi pozitive și o sumă țintă S. Fiecare tip poate fi folosit de oricâte ori. Cerem numărul minim de monede și o alegere care realizează suma. Dacă suma este imposibilă, afișăm -1.

Ideea „aleg mereu cea mai mare monedă posibilă” nu funcționează pentru orice sistem de valori. Pentru 1,3,4 și suma 6, alegerea greedy produce 4+1+1, dar optimul este 3+3. Programarea dinamică compară toate opțiunile de ultimă monedă.

Cum funcționează

Starea d[x] reprezintă numărul minim de monede cu sumă exact x. Inițializăm d[0]=0: suma zero nu cere monede. Pentru x pozitiv, încercăm fiecare valoare c[i] <= x și candidatul d[x-c[i]]+1, numai dacă suma precedentă este realizabilă. Luăm minimul candidaților.

Folosim INF=S+1 pentru o stare imposibilă. Orice sumă realizabilă x<=S folosește cel mult x monede, deoarece fiecare monedă valorează cel puțin unu. Prin urmare, INF nu poate fi confundat cu un optim valid. Marcajul descrie imposibilitatea, nu o monedă suplimentară reală.

Parcurgem sumele în ordine crescătoare. Valorile monedelor sunt strict pozitive, deci x-c[i]<x și dependența este deja calculată. O monedă de valoare zero ar invalida această argumentație, iar o valoare negativă ar putea cere o stare viitoare. Ambele sunt excluse prin restricții.

La fiecare îmbunătățire memorăm moneda aleasă în last[x]. După ce aflăm optimul, pornim de la S și scădem succesiv această monedă. Fiecare pas reduce suma și numărul optim de monede cu unu. Nu reconstruim nimic dacă d[S] este INF.

Intrarea conține n și S, apoi n valori distincte, cu 1<=n<=20, 0<=S<=1000 și 1<=c[i]<=1000. Prima linie a ieșirii conține optimul; a doua conține monedele reconstruite. Pentru S=0, a doua linie este vidă. La egalitate între soluții, păstrăm prima îmbunătățire; nu promitem o ordine lexicografică minimă.

Tabloul c are capacitate 20, dar numai n valori logice. Tablourile d și last au capacitate 1001 și folosesc indicii 0..S. Varianta std::vector alocă exact n, respectiv S+1 elemente; accesul [] și ordinea calculelor rămân neschimbate.

Exemplu urmărit pas cu pas

Pentru monedele 1,3,4 și S=6:

x       0  1  2  3  4  5  6
d[x]    0  1  2  1  1  2  2

La x=6, moneda 1 produce d[5]+1=3, moneda 3 produce d[3]+1=2, iar moneda 4 produce d[2]+1=3. Alegem 3. Reconstruirea trece prin sumele 6,3,0 și afișează 3 3. Pentru monedele 2,4, suma 3 rămâne imposibilă: toate sumele obținute sunt pare.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, s;
    std::cin >> n >> s;
    int c[20], d[1001], last[1001];
    for (int i = 0; i < n; ++i)
        std::cin >> c[i];
    const int INF = s + 1;
    d[0] = 0;
    last[0] = -1;
    for (int x = 1; x <= s; ++x) {
        d[x] = INF;
        last[x] = -1;
        for (int i = 0; i < n; ++i)
            if (c[i] <= x && d[x - c[i]] != INF && d[x - c[i]] + 1 < d[x]) {
                d[x] = d[x - c[i]] + 1;
                last[x] = c[i];
            }
    }
    if (d[s] == INF) {
        std::cout << -1 << '\n';
        return 0;
    }
    std::cout << d[s] << '\n';
    int x = s;
    while (x > 0) {
        std::cout << last[x];
        x -= last[x];
        if (x > 0)
            std::cout << ' ';
    }
    std::cout << '\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), d(s + 1), last(s + 1);
    for (int i = 0; i < n; ++i)
        std::cin >> c[i];
    const int INF = s + 1;
    d[0] = 0;
    last[0] = -1;
    for (int x = 1; x <= s; ++x) {
        d[x] = INF;
        last[x] = -1;
        for (int i = 0; i < n; ++i)
            if (c[i] <= x && d[x - c[i]] != INF && d[x - c[i]] + 1 < d[x]) {
                d[x] = d[x - c[i]] + 1;
                last[x] = c[i];
            }
    }
    if (d[s] == INF) {
        std::cout << -1 << '\n';
        return 0;
    }
    std::cout << d[s] << '\n';
    int x = s;
    while (x > 0) {
        std::cout << last[x];
        x -= last[x];
        if (x > 0)
            std::cout << ' ';
    }
    std::cout << '\n';
}

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

Orice reprezentare a lui x se termină cu o monedă permisă. Restul reprezintă exact x-c[i]. Dacă restul nu ar fi optim, l-am putea înlocui cu unul mai scurt și am îmbunătăți soluția. Examinarea tuturor ultimelor monede păstrează cel puțin o reprezentare optimă.

Sunt S stări nenule și cel mult n tranziții pentru fiecare: O(n*S) timp. Tabelul și reconstruirea folosesc O(S+n) memorie; afișarea consumă cel mult O(S) pași.

Greșeli frecvente

Nu folosi d[x]=0 pentru sume încă imposibile. Nu aplica greedy fără o demonstrație pentru valorile date. Nu accesa d[x-c[i]] înainte de verificarea c[i]<=x și nu reconstrui dintr-o stare imposibilă.

Exersează

Pentru monedele 1,5,7 și suma 10, compară greedy cu dinamica. Pentru monedele 4,6 și suma 5, explică răspunsul.

Rezolvare explicată: Greedy alege 7+1+1+1, patru monede. Dinamica găsește 5+5, două monede. Cu 4 și 6, suma 5 nu se poate obține, deci programul afișează -1.

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. Cât mai puține monede. Aplică minimizarea pentru suma exactă și tratează suma imposibilă. Aici se cere numai numărul minim, fără reconstruire; adaptează capacitatea pentru cele maximum 30 de valori.

2. Costul treptelor vizitate. Transferă ideea de cost minim de la sume la poziții. Citește atent pornirea obligatorie de pe prima treaptă și condiția de a trece după ultima.

3. Salturi până la capăt. Extensie: tranzițiile permise depind acum de poziția curentă. Minimizează numărul de salturi și detectează destinația inaccesibilă.

Continuă să înveți

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

Întrebări frecvente

Pot folosi aceeași monedă de mai multe ori?

Da, disponibilitatea fiecărui tip este nelimitată. Dacă ai un număr finit de exemplare, starea sau tranzițiile trebuie schimbate.

De ce nu sortăm valorile?

Minimul examinează toate tipurile și nu depinde de sortare. Ordinea lor influențează doar soluția aleasă la egalitate.

De ce INF este S+1?

Cel mult S monede pozitive sunt suficiente pentru orice reprezentare a unei sume de cel mult S. S+1 este strict în afara domeniului rezultatelor valide.

Cum verific reconstruirea?

Adună monedele afișate și verifică suma S. Verifică apoi că numărul lor este d[S] și că fiecare valoare apare în lista tipurilor permise.

Ce se întâmplă pentru suma zero?

Optimul este zero, iar reprezentarea este vidă. Această bază pornește tranzițiile pentru toate celelalte sume.