Struktur Data #11: Implementasi Algoritma Greedy untuk Masalah Optimasi (Coin Change, Fractional Knapsack, MST) dalam Python

Hello everyone! Selamat datang kembali di blog/laporan praktikum saya. Saya Angger Naufal Abror, mahasiswa Teknologi Informasi di Universitas Tidar. Pada pertemuan praktikum kesebelas ini, kita akan membahas salah satu paradigma algoritma yang paling intuitif dan efisien, yaitu Algoritma Greedy.

Pernah ga sihh kepikiran gimana kasir bisa ngasih kembalian dengan jumlah koin paling sedikit? kalo ngga gimana cara milih barang bawaan di ransel biar isinya paling berharga? Atau mungkin gimana ISP (penyedia layanan internet) menentukan jaringan kabel fiber optik yang menghubungkan semua kantor dengan biaya termurah? yahh jawabannya ada pada algoritma yang akan kita pelajari kali ini.

Algoritma Greedy adalah pendekatan yang mengambil keputusan terbaik pada setiap langkah (optimal lokal), dengan harapan akan mendapatkan solusi terbaik secara keseluruhan (optimal global). Paradigma ini terkenal karena kesederhanaannya dan efisiensinya dalam berbagai masalah optimasi, meskipun tidak selalu menjamin solusi optimal untuk semua kasus.

Di praktikum ini, kita akan mengimplementasikan tiga masalah klasik yang diselesaikan dengan pendekatan Greedy menggunakan Python:

1. Coin Change (masalah kembalian koin)
2. Fractional Knapsack (masalah ransel pecahan)
3. Minimum Spanning Tree (MST) menggunakan algoritma Prim dan Kruskal

Langsung saja kita mulai! 🚀

🎯 A. Tujuan Pembelajaran

Setelah menyelesaikan praktikum ini, mahasiswa diharapkan mampu:

1. Menjelaskan prinsip kerja algoritma greedy dan karakteristik masalah yang dapat diselesaikan secara optimal dengan pendekatan tersebut.
2. Mengimplementasikan algoritma greedy pada kasus Fractional Knapsack, Kruskal, dan Prim menggunakan bahasa pemrograman Python.
3. Menganalisis hasil eksekusi algoritma greedy dan membandingkan efektivitasnya dalam konteks optimasi nilai dan struktur graf.

🛠️ B. Alat dan Bahan

Praktikum ini membutuhkan perangkat dan aplikasi sebagai berikut:

• Perangkat: Laptop/PC dengan koneksi internet.
• Sistem Operasi: Windows 11 / Linux / macOS (semua bisa).
• Aplikasi: Google Colaboratory (Colab) atau Jupyter Notebook / VS Code lokal.
• Library Python: heapq (built-in, untuk priority queue di algoritma Prim)

📖 C. Dasar Teori

1. Konsep Algoritma Greedy

Dalam ilmu komputer, algoritma greedy adalah metode pemecahan masalah yang membangun solusi secara bertahap (inkremental). Pada setiap langkah, algoritma ini akan memilih pilihan yang tampak paling baik dan paling menguntungkan saat itu juga (optimal lokal), tanpa mempertimbangkan konsekuensi di masa depan atau membatalkan keputusan yang sudah diambil.

Permasalahan yang cocok diselesaikan dengan pendekatan greedy umumnya memiliki dua karakteristik utama:

1. Greedy Choice Property: Pilihan terbaik pada saat ini akan menjadi bagian dari solusi terbaik akhir.
2. Optimal Substructure: Solusi optimal dari masalah keseluruhan dapat dibentuk dari solusi optimal dari submasalahnya.

Perbedaan utama dengan dynamic programming: Dynamic programming mempertimbangkan semua kemungkinan dan menyimpan hasil submasalah untuk digunakan kembali, sementara greedy langsung memilih jalur yang terbaik saat ini tanpa meninjau kembali.

2. Sejarah Algoritma Greedy

Meskipun konsep “greedy” sudah ada sejak lama, penerapan formalnya dalam algoritma komputer berkembang pesat pada pertengahan abad ke-20. Dua algoritma terkenal yang menggunakan pendekatan greedy untuk Minimum Spanning Tree adalah:

• Algoritma Kruskal: Dikembangkan oleh Joseph Kruskal pada tahun 1956. Algoritma ini memulai dengan semua sisi graf dan secara greedy memilih sisi dengan bobot terkecil yang tidak membentuk siklus.
• Algoritma Prim: Dikembangkan oleh Robert C. Prim pada tahun 1957. Algoritma ini memulai dari satu simpul dan secara greedy menambahkan sisi dengan bobot terkecil yang menghubungkan simpul yang sudah dipilih dengan simpul yang belum dipilih.

Fakta menarik: Algoritma Prim sebenarnya pertama kali ditemukan oleh Vojtěch Jarník pada tahun 1930, sehingga kadang disebut algoritma Jarník-Prim.

3. Karakteristik Masalah Greedy

Dalam konteks pemrograman, pendekatan greedy umumnya digunakan ketika:

• Terdapat urutan pilihan yang dapat dinilai berdasarkan suatu kriteria.
• Keputusan dapat diambil tanpa mempertimbangkan solusi secara keseluruhan.
• Solusi sebagian dapat langsung dikembangkan menjadi solusi penuh tanpa koreksi.

📥 D. Langkah Praktikum

Praktikum ini saya lakukan menggunakan Google Colaboratory. Berikut adalah implementasi kode untuk setiap bagian, yang sudah saya sesuaikan dan dokumentasikan berdasarkan modul.

1. Coin Change (Masalah Kembalian Koin)

Masalah ini bertujuan mencari jumlah minimum koin yang diperlukan untuk membentuk sejumlah nilai tertentu, dengan asumsi kita memiliki koin dalam berbagai denominasi (1, 5, 10, 25) dalam jumlah tak terbatas.

Prinsip Greedy: Pada setiap langkah, pilih koin dengan nilai terbesar yang masih lebih kecil atau sama dengan sisa nilai yang harus dibayarkan.

Kode Implementasi:

def coin_change_greedy(amount, coins):
  coins.sort(reverse=True)
  result = []
  for coin in coins:
    while amount >= coin:
      amount -= coin
      result.append(coin)
  return result

# Contoh
amount = 57
coins = [25, 10, 5, 1]
change = coin_change_greedy(amount, coins)
print("Uang yang dibutuhkan:", change)

Output:

Penjelasan:

• coins.sort(reverse=True): Langkah penting yang mengimplementasikan greedy choice property. Dengan mengurutkan dari terbesar, kita memastikan selalu mencoba koin bernilai tertinggi terlebih dahulu.
• while amount >= coin: Loop ini akan terus menggunakan koin yang sama selama masih memungkinkan. Untuk amount=57 dan coin=25, loop akan berjalan 2x (sisa 7).
• result.append(coin): Mencatat setiap koin yang digunakan.

2. Fractional Knapsack (Ransel Pecahan)

Masalah ini meminta kita mengisi ransel dengan kapasitas tertentu dengan barang-barang yang memiliki nilai dan berat masing-masing. Tujuannya adalah memaksimalkan total nilai di dalam ransel. Kita diperbolehkan mengambil sebagian (fraksional) dari suatu barang.

Prinsip Greedy: Pilih barang berdasarkan rasio nilai/berat (value per weight) tertinggi terlebih dahulu.

Kode Implementasi:

def fractional_knapsack(items, capacity):
  items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
  total_value = 0.0
  for value, weight in items:
    if capacity >= weight:
      capacity -= weight
      total_value += value
    else:
      total_value += value * capacity / weight
      break
  return total_value

# Contoh
items = [(60, 10), (120, 30), (100, 20)]
capacity = 50
max_value = fractional_knapsack(items, capacity)
print("Nilai maksimum yang dapat diperoleh:", max_value)

Output:

Penjelasan:

• key=lambda x: x[0]/x[1]: Fungsi lambda ini menghitung rasio nilai/berat untuk setiap item. reverse=True mengurutkan dari rasio tertinggi.
• if capacity >= weight: Jika kapasitas masih cukup, ambil seluruh item (total_value += value).
• else: fraction = capacity / weight: Jika tidak cukup, hitung proporsi yang bisa diambil (capacity/weight) lalu kalikan dengan nilai item. break menghentikan proses karena ransel sudah penuh.

Perhitungan manual untuk contoh di atas:

• Item 0: rasio 60/10 = 6 → ambil seluruhnya (capacity sisa 40, value=60)
• Item 1: rasio 100/20 = 5 → ambil seluruhnya (capacity sisa 20, value=160)
• Item 2: rasio 120/30 = 4 → ambil 20/30 = 2/3 bagian (value += 120 * 2/3 = 80)
• Total = 60 + 100 + 80 = 240

3. Minimum Spanning Tree (MST)

Minimum Spanning Tree adalah subgraf yang menghubungkan semua simpul (vertex) dalam graf berbobot terhubung dengan total bobot minimum dan tanpa membentuk siklus. Dua algoritma greedy yang populer adalah Prim dan Kruskal.

a) Algoritma Prim

Algoritma Prim memulai dari satu simpul (start) dan secara bertahap menambahkan sisi (edge) dengan bobot terkecil yang menghubungkan simpul yang sudah dikunjungi dengan simpul yang belum.

Kode Implementasi:

import heapq
def prim_mst(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0
while min_heap:
        weight, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for neighbor, edge_weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (edge_weight, neighbor))
    return total_weight
# Graf: adjacency list 
graph = {
    'A': [('B', 2), ('C', 3)],
    'B': [('A', 2), ('C', 4), ('D', 5)],
    'C': [('A', 3), ('B', 1), ('D', 4)],
    'D': [('B', 1), ('C', 4)]
}
print(f"Total bobot MST (Prim): {prim_mst(graph, 'A')}")

Output:

Penjelasan:

• heapq: Struktur data priority queue yang selalu memberikan elemen dengan nilai terkecil. Ini implementasi sempurna untuk prinsip greedy MST.
• visited = set(): Menyimpan simpul yang sudah masuk MST. Simpul yang sudah dikunjungi tidak perlu diproses ulang.
• min_heap = [(0, start)]: Inisialisasi heap dengan simpul awal berbobot 0.
• for neighbor, edge_weight in graph[node]: Iterasi semua tetangga dari simpul saat ini, lalu tambahkan ke heap.

b) Algoritma Kruskal

Algoritma Kruskal memulai dari semua sisi graf, lalu memilih sisi dengan bobot terkecil yang tidak membentuk siklus, hingga semua simpul terhubung.

Kode Implementasi:

def kruskal_mst (edges, n_nodes) :
  parent = {i: i for i in range (n_nodes) }

  def find(x):
    while parent [x] != x:
      x = parent [x]
    return x

  def union (x, y):
    root_x = find (x)
    root_y = find(y)
    if root_x != root_y:
      parent [root_y] = root_x
      return True
    return False

  edges.sort (key=lambda x: x[2])
  total_weight = 0
  for u, v, weight in edges:
    if union (u, v) :
      total_weight += weight
  return total_weight

# edges: (node1, node2, weight), nodes are represented by integers
edges = [ (0, 1, 2), (0, 2, 3), (1, 2, 1), (1, 3, 1), (2, 3, 4)]
print("Total bobot MST (Kruskal):", kruskal_mst (edges, 4))

Output:

Penjelasan:

• heapq: Struktur data priority queue yang selalu memberikan elemen dengan nilai terkecil. Ini implementasi sempurna untuk prinsip greedy MST.
• visited = set(): Menyimpan simpul yang sudah masuk MST. Simpul yang sudah dikunjungi tidak perlu diproses ulang.
• min_heap = [(0, start)]: Inisialisasi heap dengan simpul awal berbobot 0.
• for neighbor, edge_weight in graph[node]: Iterasi semua tetangga dari simpul saat ini, lalu tambahkan ke heap.

💾 E. Dokumentasi Kode

Semua program pada praktikum ini telah didokumentasikan dan dapat diakses melalui repository GitHub saya berikut:

DATA-STRUCTURE/DataStrucrure_11.ipynb at main · ANGGER4/DATA-STRUCTURE

📚 F. Kesimpulan

Praktikum kalii ini menunjukkan bahwa algoritma greedy bekerja dengan mengambil keputusan terbaik di setiap langkah tanpa peninjauan kembali, sehingga efisien namun tidak selalu optimal. Fractional Knapsack serta MST (Prim dan Kruskal) menghasilkan solusi optimal, sedangkan Coin Change belum tentu optimal tergantung sistem koin. Kompleksitas waktu algoritma didominasi proses sorting: O(N log N) untuk Coin Change dan Fractional Knapsack, O((V+E) log V) untuk Prim, serta O(E log E) untuk Kruskal. Penggunaan struktur data seperti heapq sangat berpengaruh terhadap efisiensi. Keterbatasan greedy terlihat pada kasus 0/1 Knapsack yang memerlukan dynamic programming.

📖 G. Referensi

• Modul Praktikum Struktur Data #11 — Algoritma Greedy (Coin Change, Fractional Knapsack, MST), Universitas Tidar (2024/2025).