Fractional Knapsack

Seorang pencuri masuk ke gudang dengan tas berkapasitas terbatas. Setiap barang bisa diambil utuh atau dipotong sebagian (mis. emas batangan, pasir berlian). Tujuannya: maksimalkan nilai yang dibawa. Inilah fractional knapsack — kebalikan dari 0/1 knapsack yang memaksa pilihan biner ambil atau tinggalkan. Perbedaan kecil ini berdampak besar: fractional knapsack dapat dipecahkan dengan greedy dalam O(n log n), sementara 0/1 knapsack membutuhkan dynamic programming O(n · W). Pada Chapter ini kita akan memahami mengapa greedy optimal untuk fractional variant, mengimplementasikannya di C++, dan membandingkannya dengan 0/1 knapsack.

Aturan: Maksimalkan Nilai dengan Pecahan Diizinkan #

Diberikan n barang, masing-masing dengan berat w[i] dan nilai v[i], serta tas berkapasitas W. Kita boleh mengambil fraksi 0 ≤ f[i] ≤ 1 dari setiap barang, dengan kontribusi nilai f[i] · v[i] dan kontribusi berat f[i] · w[i]. Tujuan:

maksimalkan  Σ f[i] · v[i]
subjek       Σ f[i] · w[i] ≤ W,  0 ≤ f[i] ≤ 1

Strategi greedy:

1. Hitung rasio value/weight untuk setiap barang.
2. Sort barang descending by rasio.
3. Ambil barang utuh selama muat; bila tidak muat utuh, ambil pecahan terbesar yang muat.
4. Berhenti bila tas penuh.

Greedy choice = rasio tertinggi. Mengapa? Karena tiap kilogram yang masuk tas dari barang rasio tinggi memberi kontribusi nilai lebih besar daripada tiap kilogram dari barang rasio rendah.

Mekanisme: Mengapa Greedy Optimal #

Pembuktian informal dengan exchange argument: misalkan solusi optimal S* tidak mengandung pecahan maksimum dari barang rasio tertinggi g. Maka S* mengandung sejumlah berat dari barang rasio lebih rendah. Karena ratio(g) ≥ ratio(other), menukar sebagian berat barang lain dengan berat g yang setara tidak mengurangi total nilai, malah bisa meningkatkan. Kontradiksi dengan asumsi S* optimal.

Exchange argument ini bekerja karena fraksional memungkinkan substitusi parsial — sesuatu yang tidak mungkin di 0/1 knapsack.

Implementasi C++ #

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int id;
    double weight;
    double value;
    double ratio; // value / weight
};

// Fractional knapsack greedy — sort by ratio desc
double fractionalKnapsack(int capacity, std::vector<Item> items) {
    // Sort descending by ratio (v/w)
    std::sort(items.begin(), items.end(),
              [](const Item& a, const Item& b) {
                  return a.ratio > b.ratio;
              });

    double totalValue = 0.0;
    double remaining = capacity;

    for (const auto& it : items) {
        if (remaining <= 0) break;
        if (it.weight <= remaining) {
            // Ambil utuh
            totalValue += it.value;
            remaining -= it.weight;
            std::cout << "  Item " << it.id
                      << ": ambil utuh (" << it.weight
                      << " kg, +" << it.value << ")\n";
        } else {
            // Ambil pecahan
            double frac = remaining / it.weight;
            totalValue += frac * it.value;
            std::cout << "  Item " << it.id
                      << ": ambil pecahan " << frac * 100 << "% ("
                      << remaining << " kg, +"
                      << frac * it.value << ")\n";
            remaining = 0;
        }
    }
    return totalValue;
}

int main() {
    int capacity = 50;
    std::vector<Item> items = {
        {1, 10, 60, 6.0},
        {2, 20, 100, 5.0},
        {3, 30, 120, 4.0}
    };

    std::cout << "Kapasitas tas: " << capacity << " kg\n";
    std::cout << "Pemilihan barang:\n";
    double total = fractionalKnapsack(capacity, items);
    std::cout << "Total nilai maksimum: " << total << '\n';
    return 0;
}

Output yang Dihasilkan:

Kapasitas tas: 50 kg
Pemilihan barang:
  Item 1: ambil utuh (10 kg, +60)
  Item 2: ambil utuh (20 kg, +100)
  Item 3: ambil pecahan 66.6667% (20 kg, +80)
Total nilai maksimum: 240

Bedah Kode Baris-per-Baris #

1. struct Item { int id; double weight; double value; double ratio; };: rekam barang dengan rasio value/weight yang sudah dihitung. Menyimpan rasio eksplisit menghindari pembagian berulang saat sort.
2. std::sort(items.begin(), ..., [](...) { return a.ratio > b.ratio; }): sort descending by rasio. Kompleksitas O(n log n) — biaya dominan algoritma.
3. if (it.weight <= remaining): cek apakah barang utuh masih muat. Bila ya, ambil utuh dan kurangi sisa kapasitas.
4. totalValue += it.value; remaining -= it.weight;: tambahkan nilai penuh dan kurangi kapasitas penuh. Greedy choice penuh dijalankan.
5. double frac = remaining / it.weight;: hitung fraksi yang bisa diambil. Bila barang tidak muat utuh, ambil pecahan terbesar yang memenuhi sisa kapasitas.
6. totalValue += frac * it.value; remaining = 0;: tambahkan nilai proporsional dan tandai tas penuh.
7. Output 240: item 1 (rasio 6) utuh = 60, item 2 (rasio 5) utuh = 100, item 3 (rasio 4) pecahan 2/3 = 80. Total = 60 + 100 + 80 = 240. Inilah solusi optimal.

Trace Step-by-Step #

Kapasitas awal: 50 kg. Barang dengan rasio: {1: 6.0, 2: 5.0, 3: 4.0} (sudah descending).

Hasil akhir: total nilai 240 dengan tas penuh terisi.

Komparasi dengan 0/1 Knapsack #

Pada 0/1 knapsack, kita tidak boleh mengambil pecahan. Untuk kapasitas W = 50 dan barang yang sama, solusi optimal adalah memilih {item 2, item 3} dengan total 100 + 120 = 220. Greedy fractional yang mengambil pecahan tidak valid di sini.

Implementasi 0/1 Knapsack (Untuk Komparasi) #

Sebagai pembanding, berikut implementasi 0/1 knapsack dengan dynamic programming:

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack01(const std::vector<int>& wt,
               const std::vector<int>& val,
               int capacity) {
    int n = wt.size();
    std::vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; ++i) {
        // Iterasi mundur agar tidak pakai item yang sama dua kali
        for (int c = capacity; c >= wt[i]; --c) {
            dp[c] = std::max(dp[c], val[i] + dp[c - wt[i]]);
        }
    }
    return dp[capacity];
}

int main() {
    std::vector<int> wt = {10, 20, 30};
    std::vector<int> val = {60, 100, 120};
    int capacity = 50;

    std::cout << "0/1 Knapsack optimal: "
              << knapsack01(wt, val, capacity) << '\n';
    return 0;
}

Output yang Dihasilkan:

0/1 Knapsack optimal: 220

Bedah Kode Baris-per-Baris #

1. std::vector<int> dp(capacity + 1, 0);: array DP 1D berukuran W+1. dp[c] = max value dengan kapasitas c. Optimalisasi dari array 2D O(n·W) menjadi O(W) dengan iterasi mundur.
2. for (int c = capacity; c >= wt[i]; --c): iterasi mundur dari kapasitas maksimum ke berat item. Iterasi mundur menjamin tiap item hanya dipakai sekali — karakteristik 0/1.
3. dp[c] = std::max(dp[c], val[i] + dp[c - wt[i]]);: recurrence. Pilih antara skip item i (dp[c]) atau ambil (val[i] + dp[c - wt[i]]).
4. Output 220: ambil item 2 dan item 3 dengan total 100 + 120 = 220. Bandingkan dengan greedy fractional yang menghasilkan 240 — perbedaan 20 karena fractional membolehkan pecahan item 3.

Kompleksitas #

Aplikasi Nyata #

• Investasi portofolio: alokasi modal ke saham dengan rasio return/risk tertinggi.
• Cargo loading: kapal kargo bisa memuat kontainer penuh atau muatan curah (pasir, batubara) — pecahan diizinkan.
• Resource allocation: alokasi bandwidth jaringan dengan rasio throughput tertinggi.
• Diet optimization: pilih makanan dengan rasio nutrisi/kalori terbaik.
• Cloud compute allocation: alokasi VM dengan rasio performa/harga terbaik.

Ringkasan #

• Fractional knapsack membolehkan pengambilan pecahan barang — berbeda dari 0/1 knapsack.
• Greedy choice: barang dengan rasio value/weight tertinggi.
• Algoritma: sort by rasio descending, ambil utuh bila muat, ambil pecahan bila tidak muat.
• Kompleksitas O(n log n) — jauh lebih cepat dari 0/1 knapsack O(n · W).
• Greedy optimal karena exchange argument: substitusi parsial selalu tidak mengurangi nilai.
• Aplikasi: investasi, cargo loading, resource allocation, diet optimization.

Chapter berikutnya akan membahas Huffman Coding — algoritma kompresi data yang menggunakan greedy dengan min-heap untuk membangun prefix code optimal.