🎒Fractional Knapsack

Fractional Knapsack adalah varian dari masalah knapsack (ransel) dalam algoritma, di mana kita boleh mengambil sebagian dari suatu item (misalnya setengah, seperempat, dsb.) untuk memaksimalkan nilai total barang dalam kapasitas ransel tertentu.

🔤 Asal Kata

• Fractional 🧩 = Pecahan atau bagian
• Knapsack 🎒 = Ransel atau tas

Pada dasarnya, Knapsack Problem adalah sebuah masalah yang muncul ketika kita memiliki:

• 🎒 Sebuah tas yang memiliki kapasitas terbatas
• 📦 Barang-barang yang dapat dimasukkan ke dalam tas
• 🎯 Tujuan: Memilih barang untuk memaksimalkan nilai total yang dibawa

🔢 Jenis Knapsack Problem

1. 1️⃣ 0/1 Knapsack Problem

• ❌ Pembatasan: Kita hanya bisa memilih barang utuh
• 🚫 Tidak boleh mengambil sebagian (fractional)

1. 2️⃣ Fractional Knapsack Problem

• ✅ Fleksibilitas: Kita bisa mengambil sebagian dari barang
• 🔪 Boleh “memotong” barang sesuai kebutuhan

💡 Penjelasan Konsep Fractional Knapsack

🎯 Analogi Sederhana Bayangkan kita memiliki:

• 🎒 Sebuah tas dengan kapasitas terbatas
• 📦 Beberapa barang yang memiliki berat dan nilai tertentu
• 🎯 Tujuan: Memaksimalkan nilai barang yang dibawa

🔑 Kunci Utama

📊 Isi tas dengan barang yang memberi nilai tertinggi ⚖️ Jangan melebihi kapasitas tas ✂️ Karena fractional: Kamu boleh “potong” barang!

🏆 Contoh Praktis Misalnya kamu cuma bisa bawa 3 kg dari emas seberat 5 kg. Tidak apa-apa, yang penting nilainya tetap ikut proporsional! 💰

🎯 Keunggulan dan Kekurangan

1. ✅Keunggulan
   • 🚀 Efisien: Algoritma greedy dengan kompleksitas rendah
   • 📈 Optimal: Selalu memberikan solusi optimal untuk fractional knapsack
   • 🔧 Sederhana: Mudah dipahami dan diimplementasikan
   • 💡 Praktis: Cocok untuk masalah real-world
2. ⚠️Kekurangan
   • 🔒 Terbatas: Hanya berlaku jika item bisa dibagi (fractional)
   • ❌ Tidak cocok: Untuk 0/1 knapsack problem
   • ⚖️ Asumsi: Mengasumsikan nilai proporsional dengan berat

🌍 Aplikasi di Dunia Nyata

💼 Contoh Implementasi

• 📦 Pengiriman Barang Memaksimalkan nilai barang dalam truk dengan kapasitas terbatas Barang bisa dibagi (seperti bahan curah)

• ⛽ Alokasi Sumber Daya Distribusi bahan bakar ke berbagai lokasi Pembagian budget untuk berbagai proyek

• 🏭 Produksi Industri Memaksimalkan profit dengan bahan baku terbatas Optimasi campuran produk

• 💰 Investasi Portfolio Alokasi dana investasi untuk memaksimalkan return Diversifikasi risiko dengan batasan modal

🎓 Kesimpulan

🔑 Poin Kunci

• ✂️ Fleksibilitas: Dalam Fractional Knapsack, kita dapat memilih sebagian barang
• 🎯 Strategi Greedy: Solusinya menggunakan algoritma greedy dengan memilih barang berdasarkan rasio nilai terhadap berat tertinggi
• 📋 Langkah Sistematis: Hitung rasio → urutkan barang → masukkan barang ke tas
• ⚡ Efisiensi: Solusi ini memiliki kompleksitas waktu O(n log n)

🏆 Greedy Algorithm

Fractional Knapsack memiliki greedy choice property dan optimal substructure, sehingga pendekatan greedy garanteed menghasilkan solusi optimal.

🎯 Key Takeaway

“Prioritaskan item dengan value-to-weight ratio tertinggi, dan jangan takut untuk ‘memotong’ item terakhir jika perlu!”