Greedy: Restul cu monede

Avem un set de monede c[1], c[2], ..., c[k] și o sumă S. Cum dăm restul folosind minimum de monede?

E exemplul clasic care arată și unde greedy reușește, și unde eșuează - un studiu de caz perfect.

Greedy lacom

Sortează monedele descrescător. La fiecare pas, ia cea mai mare monedă care încape în restul rămas.

sortează descrescător c[]
total = 0
pentru fiecare monedă c din c[]:
    cnt = S / c
    folosesc cnt monede de c
    S = S - cnt * c
    total = total + cnt

Exemplu cu monede românești

Monede: 1, 5, 10, 50, 100, 500 (bani / lei).
Suma S = 287:

Total: 2 + 1 + 3 + 1 + 2 = 9 monede. Optim ✓.

Cod (greedy)

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int KMAX = 105;
int c[KMAX];
int k, S;

bool descrescator(int a, int b) {
    return a > b;
}

int main() {
    fin >> k >> S;
    for (int i = 1; i <= k; i++) {
        fin >> c[i];
    }

    sort(c + 1, c + k + 1, descrescator);

    int total = 0;
    for (int i = 1; i <= k; i++) {
        int cnt = S / c[i];
        total = total + cnt;
        S = S - cnt * c[i];
    }

    if (S > 0) {
        fout << "imposibil"; // dacă nu există monedă de 1
    } else {
        fout << total;
    }
    return 0;
}

Complexitate: O(K log K) (sortarea) + O(K) (iterare) = O(K log K).

CÂND greedy funcționează: monede „canonice”

Un set de monede e canonic dacă greedy dă optimul pentru orice sumă S ≥ 0.

Exemple de seturi canonice

• Monedele românești / euro / dolari: {1, 2, 5, 10, 20, 50, 100, ...} ✓
• Monede „de putere a lui c”: {1, c, c², c³, ...} pentru orice c ≥ 2 ✓
• {1, 5, 10, 25} (vechiul sistem american) ✓

Test rapid (informal)

Dacă, pentru fiecare monedă c[i], valoarea ei e cel puțin dublul monedei anterioare, probabil e canonic. (Nu e o garanție matematică, dar e o regulă empirică folositoare.)

CÂND greedy EȘUEAZĂ: monede non-canonice

Contraexemplul clasic

Monede: {1, 6, 10}. Sumă S = 12.

Greedy:

• Cea mai mare ≤ 12: 10 → folosesc 1 monedă, rămâne 2.
• Cea mai mare ≤ 2: 1 → folosesc 2 monede.
• Total: 1 + 2 = 3 monede.

Optim: - 6 + 6 = 2 monede.

Greedy dă 3, optimul e 2. Greedy greșește.

Alt exemplu

Monede: {1, 7, 10}, sumă 14.

Greedy: 10 + 1 + 1 + 1 + 1 = 5 monede.
Optim: 7 + 7 = 2 monede.

De ce eșuează?

Pentru că în sistemele non-canonice, alegerea celei mai mari monede nu lasă mereu ce e mai bun pentru rest. Există combinații „inteligente” cu monede mai mici care dau totalul mai eficient.

Greedy nu „vede înainte” - e prizoner al opțiunii imediate.

Soluția generală (DP)

Când greedy nu funcționează, folosim programare dinamică - răspunsul corect garantat pentru orice set de monede:

const int INF = 1e9;
const int SMAX = 1000005;
int dp[SMAX]; // dp[s] = nr minim de monede pentru suma s

void minMonedeDP(int S, int c[], int k) {
    for (int s = 0; s <= S; s++) {
        dp[s] = INF;
    }
    dp[0] = 0;
    for (int s = 1; s <= S; s++) {
        for (int i = 1; i <= k; i++) {
            int x = c[i];
            if (x <= s && dp[s - x] != INF) {
                if (dp[s - x] + 1 < dp[s]) {
                    dp[s] = dp[s - x] + 1;
                }
            }
        }
    }
    // dp[S] e răspunsul (sau INF dacă imposibil)
}

Complexitate: O(S · K). Pentru S = 10⁶, K = 10 → 10⁷ operații, OK.

Greedy vs DP - când alegi pe care?

Regulă practică: dacă enunțul specifică monedele standard (1, 5, 10, …), folosește greedy. Dacă monedele sunt arbitrare (citite din input), folosește DP.

Variantă: numărul de moduri (nu minim)

În câte moduri distincte putem da rest S cu monedele date?

Greedy nu se potrivește aici - e o problemă de numărare, nu de optim. Soluție: DP.

long long dp[SMAX]; // dp[s] = nr de moduri să formăm s

dp[0] = 1;
for (int i = 1; i <= k; i++) {          // pentru fiecare tip de monedă
    int x = c[i];
    for (int s = x; s <= S; s++) {
        dp[s] = dp[s] + dp[s - x];
    }
}

// dp[S] = numărul de moduri

(Ordinea buclelor contează - exterior pe monede, interior pe sume - pentru a evita numărarea aceleiași combinații în ordine diferită.)

Greșeli frecvente

1. Folosirea greedy fără verificarea setului de monede

Mereu întreabă: e setul „canonic”? Dacă nu ești sigur, DP.

2. Sortare crescătoare în loc de descrescătoare

Greedy începe cu cea mai mare monedă. Dacă sortezi crescător, iei cele mici → folosești mult prea multe monede.

3. Uitarea cazului „imposibil”

Dacă suma rămasă > 0 după ce ai consumat toate monedele și nu există moneda de 1, e imposibil. Tratează:

if (S > 0) fout << "imposibil";

4. DP cu memorie excesivă

Pentru S = 10⁹, DP nu încape. Dacă setul e canonic, greedy funcționează în O(K). Dacă nu e canonic și S e enorm, problema e mai grea (necesită optimizări speciale).

5. Confuzia „minim de monede” cu „număr de moduri”

Sunt probleme diferite. Verifică ce întreabă enunțul.

Ce să reții

• Greedy pentru rest: sortează descrescător, ia cea mai mare monedă posibilă la fiecare pas.
• Funcționează doar pentru seturi „canonice” (monede românești, euro, dolari).
• Eșuează pentru seturi arbitrare (ex. {1, 6, 10} → S = 12 greșește).
• Pentru orice set de monede, DP O(S · K) garantează optimul.
• DP-ul are și varianta „numărul de moduri” cu inversare a ordinii buclelor.
• Lecția generală: greedy e periculos când nu poți demonstra că e corect. Mereu testează pe contraexemple.

Probleme

pbinfoEureni→