Rangkuman: Fractional Knapsack

Greedy Algorithm

1. Pengertian

Fractional Knapsack Problem adalah masalah optimasi yang termasuk dalam kategori algoritma Greedy. Diberikan satu tas (knapsack) dengan kapasitas maksimum tertentu dan sejumlah item. Setiap item memiliki berat (weight) dan nilai (value) tertentu. Tujuannya adalah untuk mengisi tas sedemikian rupa sehingga nilai total item yang dibawa semaksimal mungkin, dengan batasan kapasitas tas. Dalam masalah ini, item dapat diambil secara parsial (pecahan), tidak harus utuh.

Karena sifatnya yang 'pecahan', masalah ini dapat diselesaikan dengan pendekatan greedy, berbeda dengan 0/1 Knapsack Problem yang lebih kompleks dan biasanya diselesaikan dengan Dynamic Programming.

2. Konsep Dasar & Pendekatan Greedy

Strategi greedy untuk Fractional Knapsack adalah dengan selalu memilih item yang memberikan nilai per unit berat (density) tertinggi. Ini memastikan bahwa kita selalu mengambil "bagian" item yang paling efisien terlebih dahulu.

Langkah-langkah Algoritma Greedy:

  1. Untuk setiap item, hitung rasio nilai per unit berat ($value / weight$).
  2. Urutkan semua item berdasarkan rasio nilai per unit berat ini secara menurun (dari yang tertinggi ke terendah).
  3. Mulai dari item dengan rasio tertinggi:
    • Jika kapasitas tas masih cukup untuk mengambil seluruh item, ambil item tersebut sepenuhnya dan kurangi kapasitas tas.
    • Jika kapasitas tas tidak cukup untuk seluruh item, ambil sebagian dari item tersebut hingga kapasitas tas terisi penuh. Hitung nilai yang diperoleh dari bagian item tersebut.
  4. Ulangi langkah 3 sampai tas penuh atau semua item sudah dipertimbangkan.

3. Contoh Ilustrasi

Misalkan Kapasitas Tas (W) = 50 kg.

Item yang tersedia:

  • Item A: Berat = 10 kg, Nilai = $60 (Rasio = 60/10 = 6)
  • Item B: Berat = 20 kg, Nilai = $100 (Rasio = 100/20 = 5)
  • Item C: Berat = 30 kg, Nilai = $120 (Rasio = 120/30 = 4)

Langkah 1 & 2: Hitung Rasio & Urutkan (terurut menurun berdasarkan rasio):

  1. Item A: Rasio = 6 (Berat: 10, Nilai: $60)
  2. Item B: Rasio = 5 (Berat: 20, Nilai: $100)
  3. Item C: Rasio = 4 (Berat: 30, Nilai: $120)

Langkah 3: Proses Pengambilan Item:

  • Ambil Item A:
    • Kapasitas sisa = 50 kg. Item A beratnya 10 kg.
    • Ambil seluruh Item A. Nilai = $60. Berat diambil = 10 kg.
    • Kapasitas sisa = 50 - 10 = 40 kg. Total Nilai = $60.
  • Ambil Item B:
    • Kapasitas sisa = 40 kg. Item B beratnya 20 kg.
    • Ambil seluruh Item B. Nilai = $100. Berat diambil = 20 kg.
    • Kapasitas sisa = 40 - 20 = 20 kg. Total Nilai = $60 + $100 = $160.
  • Ambil Item C:
    • Kapasitas sisa = 20 kg. Item C beratnya 30 kg.
    • Kapasitas tidak cukup untuk seluruh Item C. Ambil sebagian: 20 kg dari 30 kg.
    • Nilai yang diambil dari Item C = (20/30) * $120 = (2/3) * $120 = $80.
    • Kapasitas sisa = 20 - 20 = 0 kg (tas penuh). Total Nilai = $160 + $80 = $240.

Nilai Maksimal yang Didapat: $240

4. Pseudocode Algoritma


FUNCTION FractionalKnapsack(items, capacity):
    // Hitung rasio nilai/berat untuk setiap item
    FOR EACH item IN items:
        item.ratio = item.value / item.weight

    // Urutkan item berdasarkan rasio secara menurun
    SORT items by item.ratio in descending order

    total_value = 0
    current_capacity = capacity

    FOR EACH item IN items:
        IF current_capacity == 0:
            BREAK // Tas sudah penuh

        IF item.weight <= current_capacity:
            // Ambil seluruh item
            total_value = total_value + item.value
            current_capacity = current_capacity - item.weight
        ELSE:
            // Ambil sebagian item
            fraction = current_capacity / item.weight
            total_value = total_value + (item.value * fraction)
            current_capacity = 0 // Tas penuh
            BREAK // Tas sudah penuh

    RETURN total_value

5. Kompleksitas Waktu & Ruang

  • Kompleksitas Waktu:
    • Menghitung rasio: $O(N)$
    • Pengurutan item: $O(N \log N)$, di mana N adalah jumlah item.
    • Mengisi tas: $O(N)$ (sekali iterasi setelah pengurutan).
    • Total: $O(N \log N)$
  • Kompleksitas Ruang: $O(N)$ untuk menyimpan item dan rasio.

6. Aplikasi

  • Pemilihan rute pengiriman yang paling efisien berdasarkan nilai dan biaya.
  • Alokasi sumber daya dengan batasan anggaran untuk memaksimalkan keuntungan.
  • Pemilihan portofolio investasi untuk memaksimalkan return.
Kembali ke Materi Materi Selanjutnya