Strategi greedy

Greedy (rakus) adalah strategi mengambil pilihan yang terlihat paling baik saat ini, tanpa memikirkan akibatnya nanti. Greedy sangat cepat dan mudah ditulis, tetapi tidak selalu menghasilkan jawaban terbaik.

Contoh berhasil: uang kembalian

Untuk memberi kembalian dengan lembar sesedikit mungkin, ambil pecahan terbesar yang masih muat, berulang-ulang.

1PECAHAN = [100000, 50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100]23def kembalian(jumlah):4    hasil = []5    for p in PECAHAN:6        while jumlah >= p:7            hasil.append(p)8            jumlah -= p9    return hasil1011lembar = kembalian(87600)12print(lembar)13print("Banyak lembar dan koin:", len(lembar))

[50000, 20000, 10000, 5000, 2000, 500, 100]
Banyak lembar dan koin: 7

Untuk susunan pecahan seperti rupiah, greedy terbukti selalu memberi jumlah lembar paling sedikit.

Contoh gagal

Bayangkan sebuah negara dengan koin 1, 3, dan 4. Untuk membayar 6:

• Greedy mengambil 4, lalu 1, lalu 1: 3 koin.
• Jawaban terbaik adalah 3 + 3: 2 koin.

1def kembalian_greedy(jumlah, koin):2    hasil = []3    for k in sorted(koin, reverse=True):4        while jumlah >= k:5            hasil.append(k)6            jumlah -= k7    return hasil89print(kembalian_greedy(6, [1, 3, 4]))

[4, 1, 1]

Untuk koin sembarang, dibutuhkan teknik lain bernama dynamic programming, yang dibahas di kursus Desain dan Analisis Algoritma.

Contoh klasik: memilih kegiatan

Ada beberapa kegiatan dengan jam mulai dan jam selesai. Kamu ingin mengikuti sebanyak mungkin kegiatan tanpa bentrok. Strategi greedy yang benar: selalu pilih kegiatan yang selesai paling awal di antara yang masih bisa diikuti.

1kegiatan = [(8, 10), (9, 12), (10, 11), (11, 14), (13, 15), (12, 13)]2kegiatan.sort(key=lambda k: k[1])34terpilih = []5selesai_terakhir = 06for mulai, selesai in kegiatan:7    if mulai >= selesai_terakhir:8        terpilih.append((mulai, selesai))9        selesai_terakhir = selesai10print(terpilih)

[(8, 10), (10, 11), (12, 13), (13, 15)]

Memilih yang selesai paling awal menyisakan waktu sebanyak mungkin untuk kegiatan berikutnya. Strategi greedy lain, seperti memilih yang mulai paling awal atau yang paling singkat, bisa gagal pada contoh tertentu.

1PECAHAN = [100000, 50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100]23def kembalian(jumlah):4    hasil = {}5    for p in PECAHAN:6        while jumlah >= p:7            hasil[p] = hasil.get(p, 0) + 18            jumlah -= p9    return hasil1011for pecahan, banyak in kembalian(43700).items():12    print(f"Rp{pecahan}: {banyak}")

Rp20000: 2
Rp2000: 1
Rp1000: 1
Rp500: 1
Rp200: 1