Apa itu Fractional Knapsack Problem?
Fractional Knapsack Problem adalah masalah optimisasi yang menggunakan pendekatangreedy untuk memilih item dengan nilai maksimum yang dapat dimasukkan ke dalam knapsack dengan kapasitas terbatas. Berbeda dengan 0/1 Knapsack Problem, dalam masalah ini, item dapat diambil secara fraksional (sebagian), bukan hanya secara keseluruhan.
Masalah ini memiliki aplikasi dalam berbagai bidang, seperti:
- Manajemen sumber daya:Alokasi sumber daya terbatas seperti anggaran atau waktu
- Optimisasi portofolio:Pemilihan investasi dengan return maksimum
- Logistik: Memaksimalkan muatan dalam kendaraan dengan kapasitas terbatas
- Pengolahan data: Seleksi data berdasarkan prioritas dalam sistem terbatas
Cara Kerja Fractional Knapsack Problem
Algoritma greedy untuk Fractional Knapsack Problem memilih item berdasarkan rasio nilai per berat (value/weight) tertinggi. Berikut langkah-langkahnya:
- Hitung rasio nilai/berat:
- Untuk setiap item, hitung rasio nilai/berat (value/weight)
- Urutkan item:
- Urutkan item berdasarkan rasio nilai/berat secara descending
- Pilih item:
- Mulai dari item dengan rasio tertinggi
- Jika berat item <= kapasitas knapsack, ambil item secara penuh
- Jika berat item > kapasitas knapsack, ambil fraksi dari item
- Perbarui kapasitas knapsack dan akumulasikan nilai total
Pendekatan ini menjamin solusi optimal untuk memaksimalkan nilai total dalam knapsack dengan kapasitas terbatas.
Contoh Permasalahan
Misalkan kita memiliki knapsack dengan kapasitas 50 unit dan item berikut:
| Item | Nilai | Berat | Rasio (Nilai/Berat) |
|---|---|---|---|
| I1 | 60 | 10 | 6 |
| I2 | 100 | 20 | 5 |
| I3 | 120 | 30 | 4 |
Kapasitas knapsack: 50 unit
Item yang dipilih: I1 (penuh), I2 (penuh), I3 (1/3 bagian) (ditandai hijau)
Langkah-langkah solusi:
- Urutkan berdasarkan rasio: I1(6), I2(5), I3(4)
- Ambil I1: nilai=60, berat=10, sisa kapasitas=50-10=40
- Ambil I2: nilai=100, berat=20, sisa kapasitas=40-20=20
- Ambil 20/30 dari I3: nilai=(20/30)*120=80, berat=20, sisa kapasitas=0
- Nilai total: 60+100+80=240
Implementasi Kode (Python)
Berikut implementasi Fractional Knapsack Problem menggunakan Python:
def fractional_knapsack(values, weights, capacity):
# Buat daftar item dengan rasio nilai/berat
items = [(v/w, v, w) for v, w in zip(values, weights)]
# Urutkan berdasarkan rasio (descending)
items.sort(reverse=True)
total_value = 0
remaining_capacity = capacity
for ratio, value, weight in items:
if remaining_capacity >= weight:
# Ambil item penuh
total_value += value
remaining_capacity -= weight
else:
# Ambil fraksi dari item
fraction = remaining_capacity / weight
total_value += value * fraction
remaining_capacity = 0
break
return total_value
# Contoh penggunaan
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
max_value = fractional_knapsack(values, weights, capacity)
print("Nilai maksimum:", max_value)
</pre>
<p className="mt-4 leading-relaxed">
Output akan menampilkan nilai maksimum yang dapat dicapai dalam knapsack.
</p>
</section>
{/* Implementasi Kode (JavaScript) */}
<section className="mb-10 p-6 rounded-lg bg-lightBlue shadow-lg">
<h2 className="text-3xl font-semibold text-accentBlue mb-4">
Implementasi Kode (JavaScript)
</h2>
<p className="mb-4 leading-relaxed">
Berikut implementasi yang sama dalam JavaScript:
</p>
<pre className="bg-darkBlue text-textLight p-4 rounded-md overflow-x-auto text-sm">
function fractionalKnapsack(values, weights, capacity) {
// Buat array item dengan rasio nilai/berat
const items = values.map((value, i) => ({
ratio: value / weights[i],
value,
weight: weights[i]
}));
// Urutkan berdasarkan rasio (descending)
items.sort((a, b) => b.ratio - a.ratio);
let totalValue = 0;
let remainingCapacity = capacity;
for (let item of items) {
if (remainingCapacity >= item.weight) {
// Ambil item penuh
totalValue += item.value;
remainingCapacity -= item.weight;
} else {
// Ambil fraksi dari item
const fraction = remainingCapacity / item.weight;
totalValue += item.value * fraction;
remainingCapacity = 0;
break;
}
}
return totalValue;
}
// Contoh penggunaan
const values = [60, 100, 120];
const weights = [10, 20, 30];
const capacity = 50;
const maxValue = fractionalKnapsack(values, weights, capacity);
console.log("Nilai maksimum:", maxValue);
Kompleksitas dan Optimasi
Kompleksitas Waktu:
Kompleksitas waktu adalah O(n log n) karena langkah pengurutan mendominasi proses, di mana n adalah jumlah item.
Kompleksitas Ruang:
Kompleksitas ruang adalah O(n) untuk menyimpan daftar item yang diurutkan.
Optimasi:
- Pre-sorting: Jika data sudah diurutkan, kompleksitas waktu menjadi O(n)
- Parallel sorting:Menggunakan algoritma pengurutan paralel untuk data besar
- In-place sorting: Mengurangi penggunaan memori tambahan selama pengurutan
Kelebihan dan Kekurangan
Kelebihan Fractional Knapsack Problem:
- Efisien: Memberikan solusi optimal dengan kompleksitas rendah
- Fleksibel: Memungkinkan pengambilan fraksi item, cocok untuk banyak aplikasi
- Sederhana: Algoritma greedy mudah diimplementasikan
Kekurangan Fractional Knapsack Problem:
- Asumsi fraksional: Tidak cocok untuk item yang tidak dapat dibagi (misalnya, 0/1 Knapsack)
- Data harus diurutkan:Membutuhkan langkah pengurutan awal
- Keterbatasan kriteria:Hanya optimal untuk rasio nilai/berat
Kesimpulan
Fractional Knapsack Problem adalah contoh klasik dari penggunaan algoritma greedy untuk menyelesaikan masalah optimisasi. Dengan memilih item berdasarkan rasio nilai/berat tertinggi, algoritma ini memastikan nilai maksimum dalam knapsack dengan kapasitas terbatas. Meskipun memiliki keterbatasan seperti ketidakmampuan untuk menangani item yang tidak dapat dibagi, algoritma ini sangat efisien dan banyak digunakan dalam aplikasi manajemen sumber daya dan optimisasi.