Belajar Algoritm - Greedy Algorithms

#Pendahuluan

Setelah di episode 12 kita menutup FASE 3 dengan bit manipulation, pada episode ini kita memulai FASE 4: GREEDY & DYNAMIC PROGRAMMING dengan Greedy Algorithms. Greedy membuat pilihan lokal optimal di setiap langkah dengan harapan menghasilkan global optimal — cepat dan elegan, tetapi tidak selalu benar. Membedakan kapan greedy bisa dipakai dan kapan tidak adalah salah satu keterampilan paling penting dalam merancang algoritma.

Greedy menjadi powerful ketika masalah memiliki dua properti kunci: greedy choice property (pilihan lokal optimal mengarah ke global optimal) dan optimal substructure (solusi optimal masalah besar mengandung solusi optimal sub-masalah). Tanpa properti ini, greedy akan menghasilkan solusi yang salah.

#Greedy Choice Property & Optimal Substructure

#Greedy Choice Property

Pilihan lokal yang dibuat sekarang (tanpa melihat ke belakang) adalah bagian dari solusi optimal. Artinya, kita tidak perlu mempertimbangkan alternatif — pilihan greedy sudah cukup.

#Optimal Substructure

Solusi optimal masalah besar mengandung solusi optimal dari sub-masalah yang lebih kecil. Ini memungkinkan greedy membangun solusi dari bagian-bagian kecil.

Kedua properti ini harus dibuktikan secara formal untuk setiap masalah sebelum menggunakan greedy. Tanpa bukti, greedy bisa gagal — seperti Travelling Salesman Problem di mana greedy (nearest neighbor) tidak menghasilkan rute optimal.

#Activity Selection

Activity selection: diberikan aktivitas dengan waktu mulai dan selesai, pilih maksimum aktivitas yang tidak saling tumpang tindih. Greedy: pilih aktivitas yang selesai paling awal.

def activity_selection(activities):
    """activities: list of (start, finish) tuples"""
    sorted_acts = sorted(activities, key=lambda x: x[1])
    result = [sorted_acts[0]]
    last_finish = sorted_acts[0][1]
    for act in sorted_acts[1:]:
        if act[0] >= last_finish:
            result.append(act)
            last_finish = act[1]
    return result

Mengapa greedy works: memilih aktivitas yang selesai paling awal memberikan waktu paling banyak untuk aktivitas berikutnya. Jika ada solusi optimal yang tidak memilih aktivitas pertama (selesai paling awal), kita bisa menggantinya tanpa kehilangan jumlah aktivitas → greedy choice property terpenuhi.

#Huffman Coding

Huffman coding menghasilkan prefix code optimal untuk kompresi data. Karakter dengan frekuensi tinggi mendapat kode pendek; frekuensi rendah mendapat kode panjang.

#Algoritma

1. Buat min-heap dari semua karakter berdasarkan frekuensi.
2. Ambil dua node dengan frekuensi terkecil, gabung menjadi satu node (frekuensi gabungan).
3. Ulangi sampai tersisa satu node (root).
4. Kode: kiri = 0, kanan = 1, traversal dari root ke leaf.

import heapq
 
def huffman_codes(freq):
    """freq: dict {char: frequency}"""
    heap = [[f, [c, ""]] for c, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        merged = [lo[0] + hi[0]] + lo[1:] + hi[1:]
        heapq.heappush(heap, merged)
    return {pair[0]: pair[1] for pair in heap[0][1:]}
 
# Contoh
codes = huffman_codes({'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5})
# 'a': '0', 'b': '101', 'c': '100', 'd': '111', 'e': '1101', 'f': '1100'

Korektivitas: Huffman tree menghasilkan expected code length minimum untuk prefix code — terbukti dengan sifat greedy yang selalu menggabungkan dua frekuensi terkecil.

#Fractional Knapsack

Fractional knapsack: item bisa diambil sebagian (bukan biner seperti 0/1 knapsack). Greedy: ambil berdasarkan rasio value/weight tertinggi.

def fractional_knapsack(values, weights, capacity):
    items = sorted(zip(values, weights), 
                   key=lambda x: x[0]/x[1], reverse=True)
    total = 0
    for v, w in items:
        if capacity >= w:
            total += v
            capacity -= w
        else:
            total += v * (capacity / w)
            break
    return total

#Kapan Greedy Gagal?

Greedy gagal ketika greedy choice property tidak terpenuhi. Contoh klasik: coin change (minimum koin).

# Greedy coin change — TIDAK selalu optimal
# Koin: [1, 3, 4], target: 6
# Greedy: 4 + 1 + 1 = 3 koin
# Optimal: 3 + 3 = 2 koin

Greedy memilih koin terbesar dulu — tetapi tidak selalu menghasilkan jumlah minimum. Solusi: dynamic programming (episode 14).

#Penutup

Pada episode 13 ini, kalian telah memahami:

• Greedy choice property dan optimal substructure — dua syarat wajib sebelum menggunakan greedy.
• Activity selection: pilih selesai paling awal → maksimum aktivitas.
• Huffman coding: gabung frekuensi terkecil → prefix code optimal.
• Fractional knapsack: greedy rasio value/weight → solusi optimal.
• Greedy gagal: coin change dengan denominasi arbitrary → perlu DP.

Di episode 14 selanjutnya kita akan membahas Dynamic Programming Fundamentals — overlapping subproblems, optimal substructure, memoization vs tabulation, dan pola 1D state. Sampai jumpa di episode 14!