Greedy (artinya serakah) adalah cara menyelesaikan masalah dengan selalu mengambil pilihan yang paling bagus saat ini, tanpa memikirkan langkah sesudahnya. Caranya simpel dan cepat, tapi hasil akhirnya belum tentu yang terbaik. Contoh paling gampang: kasir yang memberi kembalian dengan koin sesedikit mungkin, selalu ambil pecahan terbesar dulu.
🧪 Tebakan cepat: koin yang ada cuma 4, 3, dan 1, dan kamu harus membayar 6. Greedy memakai berapa koin, dan apa ada cara yang lebih sedikit? Tebak dulu, jawabannya ada di bagian "Saat greedy kalah".
Ambil koin terbesar yang masih muat
Bayar 67 sen dengan koin [25, 10, 5, 1]:
| Langkah | Sisa | Koin terbesar yang muat | Sisa sesudahnya |
|---|---|---|---|
| 1 | 67 | 25 | 42 |
| 2 | 42 | 25 | 17 |
| 3 | 17 | 10 | 7 |
| 4 | 7 | 5 | 2 |
| 5 | 2 | 1 | 1 |
| 6 | 1 | 1 | 0 |
Hasilnya 6 koin. Tiap langkah cuma melihat sisa saat itu dan mengambil koin terbesar yang gak melebihi sisa.
function greedyCoins(amount, coins) {
const result = [];
for (const coin of coins) {
while (amount >= coin) {
result.push(coin);
amount -= coin;
}
}
return result;
}
console.log(greedyCoins(67, [25, 10, 5, 1])); // [25, 25, 10, 5, 1, 1]
console.log(greedyCoins(67, [25, 10, 5, 1]).length); // 6
coinsditulis urut dari yang terbesar, jadifor...ofmencoba koin terbesar dulu.while (amount >= coin)mengambil koin yang sama berulang kali selama masih muat. Pakai>=: koin 5 masih muat untuk sisa 5.- Tiap kali ambil, koinnya masuk
resultdanamountdikurangi nilai koin itu. - Kalau
amount0, gak ada koin yang diambil, dan hasilnya array kosong.
Kalau yang ditanya cuma banyaknya koin, ganti result.push(coin) dengan penghitung yang mulai dari 0 (jumlahKoin++), lalu kembalikan penghitungnya. Contoh lain: 41 sen jadi 25 + 10 + 5 + 1, empat koin.
Saat greedy kalah
Dengan koin [4, 3, 1] dan jumlah 6, greedy mengambil 4 dulu karena paling besar. Sisanya 2, jadi diisi 1 + 1. Totalnya 3 koin. Padahal 3 + 3 cuma 2 koin. Itu jawaban tebakan tadi: greedy kalah.
Masalahnya, koin 4 kelihatan paling bagus di langkah pertama, tapi justru menutup jalan ke jawaban yang lebih baik. Greedy gak pernah mundur untuk mengganti pilihannya.
Untuk koin [25, 10, 5, 1], greedy selalu dapat jumlah koin paling sedikit (set koin seperti ini disebut kanonik). Untuk koin sembarang, pakai dynamic programming (DP) dari materi Memoization: DP menghitung jawaban terbaik untuk semua jumlah kecil dulu, dari 1 sampai target, jadi lebih lambat tapi selalu benar. Jadi greedy cepat dan simpel, DP lebih lambat tapi pasti dapat yang terbaik.
⚠️ Jebakan yang sering ketemu
- Koin urut dari kecil. Dengan
[1, 5, 10, 25], koin 1 diambil terus sampai sisanya habis. Greedy butuh koin terbesar di depan. ifdi tempatwhile.ifcuma mengambil satu koin tiap jenis, padahal 67 butuh dua koin 25.- Mengembalikan daftar koin. Kalau yang diminta banyaknya koin, kembalikan angka (
result.lengthatau penghitung), bukan array.
💡 Cara mengecek greedy. Sebelum percaya greedy, coba beberapa jumlah kecil dan bandingkan dengan jawaban DP atau hitungan tangan. Satu contoh di mana greedy kalah sudah cukup untuk membuktikan greedy gak bisa dipakai di soal itu.
TL;DR: Greedy selalu mengambil pilihan terbaik saat ini dan gak pernah mundur. Untuk kembalian: urutkan koin dari terbesar, ambil tiap koin pakai while (amount >= coin) selama masih muat, kurangi sisanya, dan hitung koinnya. Dengan [25, 10, 5, 1] hasil greedy selalu paling sedikit (41 jadi 4 koin). Dengan [4, 3, 1] untuk 6, greedy dapat 3 koin padahal 3 + 3 cuma 2. Kalau greedy belum terbukti benar, pakai DP.
