// Contoh Bab 12: greedy yang benar untuk satu himpunan koin, salah untuk
// himpunan koin yang lain.
//
// Compile:  g++ -std=c++17 -O2 -o koingagal exercises/12/02-koin-gagal.cpp
// Jalankan: ./koingagal

#include <iostream>
using namespace std;

const int BESAR = 1000000;

int koin[10];
int banyak_koin;

int greedy(int k) {
    int jumlah = 0;
    for (int i = 0; i < banyak_koin; i++) {      // koin terurut menurun
        jumlah += k / koin[i];
        k %= koin[i];
    }
    return (k == 0) ? jumlah : BESAR;
}

int terbaik(int k) {
    // dp sederhana: jumlah koin paling sedikit untuk setiap nilai 0..k
    static int dp[1005];
    dp[0] = 0;
    for (int v = 1; v <= k; v++) {
        dp[v] = BESAR;
        for (int i = 0; i < banyak_koin; i++)
            if (v >= koin[i] && dp[v - koin[i]] + 1 < dp[v])
                dp[v] = dp[v - koin[i]] + 1;
    }
    return dp[k];
}

void uji(const char *nama, int daftar[], int n, int batas) {
    banyak_koin = n;
    for (int i = 0; i < n; i++) koin[i] = daftar[i];

    cout << nama << ": ";
    bool ada_beda = false;
    for (int k = 1; k <= batas; k++) {
        if (greedy(k) != terbaik(k)) {
            cout << "greedy salah pada k = " << k
                 << " (greedy " << greedy(k)
                 << ", terbaik " << terbaik(k) << ")\n";
            ada_beda = true;
            break;
        }
    }
    if (!ada_beda) cout << "greedy benar untuk semua k <= " << batas << "\n";
}

int main() {
    int buatan[] = {4, 3, 1};              // harus terurut menurun
    int amerika[] = {25, 10, 5, 1};

    uji("pecahan {1,3,4}", buatan, 3, 100);
    uji("pecahan {1,5,10,25}", amerika, 4, 100);

    // Coba ini: tambahkan pecahan lain dan cari yang membuat greedy gagal.
    return 0;
}