FRACTIONAL KNAPSACK

FRACTIONAL KNAPSACK

---

Pengantar

Apa itu Knapsack Problem?
Masalah optimisasi untuk memilih item sehingga nilai total maksimal tanpa melebihi kapasitas tas.
Terdiri dari dua variasi utama:

• 0/1 Knapsack: Tidak boleh mengambil sebagian barang
• Fractional Knapsack: Boleh mengambil sebagian barang
  Fractional Knapsack lebih sederhana dan efisien, diselesaikan dengan algoritma greedy.

---

Definisi Fractional Knapsack

Masalah optimisasi dalam algoritma dan struktur data.
Tujuan: Memaksimalkan nilai barang dalam knapsack dengan kemungkinan mengambil fraksi barang.

---

Karakteristik Fractional Knapsack

• Tiap barang punya berat dan nilai
• Kapasitas tas terbatas
• Barang bisa diambil sebagian
• Solusi menggunakan pendekatan greedy

---

Strategi Penyelesaian (Greedy)

1. Hitung rasio value / weight tiap item
2. Urutkan item berdasarkan rasio tertinggi
3. Ambil sebanyak mungkin dari item tertinggi
4. Jika tak muat, ambil sebagian dari item terakhir

---

Kompleksitas Waktu

• Sorting: O(n log n)
• Pengambilan barang: O(n)

---

Aplikasi

• Penjadwalan tugas
• Investasi proyek
• Pengalokasian bandwidth
• Optimisasi logistik

---

Tentang Algoritma Greedy

Ciri-ciri:

• Pilihan lokal optimal di setiap langkah
• Tidak mempertimbangkan konsekuensi ke depan
• Implementasi sederhana dan cepat

Kelemahan:

• Tidak selalu menghasilkan solusi optimal global

---

Kesimpulan

Fractional Knapsack dapat diselesaikan efisien dengan greedy.
Mengambil barang berdasarkan rasio nilai terhadap berat mengarah pada solusi optimal global.
Lebih ringan dari 0/1 Knapsack karena tidak perlu eksplorasi kombinatorial.

---

Terima Kasih 🙏