import java.util.Arrays;

public class GreedyKoin {

    public static void main(String[] args) {
        // Denominasi koin rupiah, urut menurun untuk strategi greedy.
        int[] denominasi = {10000, 5000, 2000, 1000, 500, 200, 100};
        int jumlah = 73500;

        System.out.println("=== Kembalian Rp" + jumlah + " dengan greedy ===");
        int[] hasil = kembalianGreedy(denominasi, jumlah);
        for (int i = 0; i < denominasi.length; i++) {
            if (hasil[i] > 0) {
                System.out.printf("  Rp%-6d x %d%n", denominasi[i], hasil[i]);
            }
        }
        System.out.println("Total keping koin: " + totalKeping(hasil));

        System.out.println();
        System.out.println("=== Kontra-contoh: denominasi {25, 10, 1}, jumlah 30 ===");
        int[] khayalan = {25, 10, 1};
        int[] hasilGreedy = kembalianGreedy(khayalan, 30);
        System.out.println("Greedy  : " + deskripsi(khayalan, hasilGreedy)
                + " -> " + totalKeping(hasilGreedy) + " keping");
        System.out.println("Optimal : " + koinMinDP(khayalan, 30)
                + " keping (dihitung dengan dynamic programming)");
    }

    // Greedy: ambil koin terbesar yang masih muat, ulangi pada sisanya.
    static int[] kembalianGreedy(int[] denominasi, int jumlah) {
        int[] hasil = new int[denominasi.length];
        int sisa = jumlah;
        for (int i = 0; i < denominasi.length && sisa > 0; i++) {
            hasil[i] = sisa / denominasi[i];
            sisa %= denominasi[i];
        }
        return hasil;
    }

    // Pembanding optimal: coin change via tabel DP sederhana.
    static int koinMinDP(int[] koin, int jumlah) {
        int[] terbaik = new int[jumlah + 1];
        Arrays.fill(terbaik, Integer.MAX_VALUE);
        terbaik[0] = 0;
        for (int n = 1; n <= jumlah; n++) {
            for (int k : koin) {
                if (k <= n && terbaik[n - k] != Integer.MAX_VALUE) {
                    terbaik[n] = Math.min(terbaik[n], terbaik[n - k] + 1);
                }
            }
        }
        return terbaik[jumlah];
    }

    static int totalKeping(int[] hasil) {
        int total = 0;
        for (int h : hasil) {
            total += h;
        }
        return total;
    }

    static String deskripsi(int[] denominasi, int[] hasil) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < denominasi.length; i++) {
            if (hasil[i] > 0) {
                if (!sb.isEmpty()) {
                    sb.append(" + ");
                }
                sb.append(denominasi[i]).append("x").append(hasil[i]);
            }
        }
        return sb.toString();
    }
}