Knapsack

Knapsack adalah masalah DP paling fundamental yang melibatkan keputusan optimasi: pilih subset item dengan total nilai maksimal tanpa melebihi kapasitas. Pada 0/1 knapsack, setiap item hanya boleh diambil atau dilewati — tidak boleh diambil sebagian. Masalah ini menjadi template untuk banyak DP lainnya seperti subset sum, partition equal subset sum, dan target sum. Pada Chapter ini kita akan membedah state dan transisi 0/1 knapsack, optimasi ruang dari 2D ke 1D, dan rekonstruksi solusi (item mana yang dipilih).

Aturan: 0/1 — Ambil atau Lewati #

Diberikan:

n item, masing-masing dengan bobot w[i] dan nilai v[i].
Kapasitas tas W.

Tujuan: pilih subset S ⊆ {0, 1, ..., n-1} sehingga sum(w[i] for i in S) <= W dan sum(v[i] for i in S) maksimal.

Mekanisme: State 2D dan Transisi #

State: dp[i][cap] — nilai maksimum yang bisa dicapai mempertimbangkan item 0..i-1 dengan kapasitas cap.

Base case: dp[0][cap] = 0 untuk semua cap (tidak ada item, tidak ada nilai).

Transisi: untuk setiap item i-1 dengan kapasitas cap:

text
dp[i][cap] = dp[i-1][cap]                              // lewati item i-1
           (jika w[i-1] <= cap) max dengan
           dp[i-1][cap - w[i-1]] + v[i-1]              // ambil item i-1

flowchart TD A["dp i cap"] --> B["Pilihan 1: lewati"] A --> C["Pilihan 2: ambil (jika w[i-1] <= cap)"] B --> D["dp i-1 cap"] C --> E["dp i-1 cap - w[i-1] + v[i-1]"] D --> F["max"] E --> F F --> G["dp i cap = hasil"]

Kode: 0/1 Knapsack 2D #

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

int knapsack_2d(const std::vector<int>& w, const std::vector<int>& v, int W) {
    int n = static_cast<int>(w.size());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int cap = 0; cap <= W; ++cap) {
            dp[i][cap] = dp[i - 1][cap];  // lewati
            if (w[i - 1] <= cap) {
                dp[i][cap] = std::max(dp[i][cap],
                                      dp[i - 1][cap - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return dp[n][W];
}

int main() {
    std::vector<int> w = {2, 3, 4, 5};
    std::vector<int> v = {3, 4, 5, 6};
    int W = 8;
    std::cout << "Nilai maksimum = " << knapsack_2d(w, v, W) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Nilai maksimum = 10

Baris std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));: tabel DP 2D berukuran (n+1) × (W+1). Indeks i berarti “item yang sudah dipertimbangkan: 0..i-1”.
Baris dp[i][cap] = dp[i - 1][cap];: opsi lewati — nilai tidak berubah dari item sebelumnya.
Baris if (w[i - 1] <= cap): item muat di kapasitas saat ini.
Baris dp[i - 1][cap - w[i - 1]] + v[i - 1]: opsi ambil — kapasitas berkurang w[i-1], nilai bertambah v[i-1]. Sub-masalah dp[i-1][cap-w[i-1]] sudah dihitung sebelumnya.
Hasil 10: ambil item 1 (bobot 3, nilai 4) dan item 3 (bobot 5, nilai 6). Total bobot 8, nilai 10. Optimal.

Optimasi Ruang: 2D ke 1D #

Karena dp[i][cap] hanya bergantung pada dp[i-1][*], kita bisa menggunakan array 1D. Loop kapasitas mundur agar tidak memakai item yang sama dua kali:

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

int knapsack_1d(const std::vector<int>& w, const std::vector<int>& v, int W) {
    int n = static_cast<int>(w.size());
    std::vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i) {
        // Loop mundur: cap dari W ke w[i]
        for (int cap = W; cap >= w[i]; --cap) {
            dp[cap] = std::max(dp[cap], dp[cap - w[i]] + v[i]);
        }
    }
    return dp[W];
}

int main() {
    std::vector<int> w = {2, 3, 4, 5};
    std::vector<int> v = {3, 4, 5, 6};
    int W = 8;
    std::cout << "Nilai maksimum (1D) = " << knapsack_1d(w, v, W) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Nilai maksimum (1D) = 10

Baris std::vector<int> dp(W + 1, 0);: array 1D. Penghematan memori dari O(n·W) menjadi O(W).
Baris for (int cap = W; cap >= w[i]; --cap): loop mundur sangat penting. dp[cap - w[i]] harus merujuk ke iterasi i-1 (sebelum item i dipakai). Loop mundur menjamin hal ini.
Baris dp[cap] = std::max(dp[cap], dp[cap - w[i]] + v[i]);: transisi inti. dp[cap] (sebelum update) = “lewatkan item i”. dp[cap - w[i]] + v[i] = “ambil item i”.
Hasil identik 10: optimasi ruang tidak mengubah jawaban.

Unbounded Knapsack #

Bila item boleh dipakai tak terbatas kali, loop kapasitas maju:

cpp
for (int i = 0; i < n; ++i) {
    for (int cap = w[i]; cap <= W; ++cap) {
        dp[cap] = std::max(dp[cap], dp[cap - w[i]] + v[i]);
    }
}

Loop maju memungkinkan item i dipakai beberapa kali karena dp[cap - w[i]] mungkin sudah memakai item i.

Rekonstruksi Solusi #

Untuk mengetahui item mana yang dipilih, kita traceback dari dp[n][W]:

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

int main() {
    std::vector<int> w = {2, 3, 4, 5};
    std::vector<int> v = {3, 4, 5, 6};
    int W = 8;
    int n = static_cast<int>(w.size());

    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int cap = 0; cap <= W; ++cap) {
            dp[i][cap] = dp[i - 1][cap];
            if (w[i - 1] <= cap) {
                dp[i][cap] = std::max(dp[i][cap],
                                      dp[i - 1][cap - w[i - 1]] + v[i - 1]);
            }
        }
    }

    std::cout << "Nilai maksimum = " << dp[n][W] << '\n';

    // Traceback: cari item mana yang dipilih
    std::vector<int> chosen;
    int cap = W;
    for (int i = n; i >= 1; --i) {
        if (dp[i][cap] != dp[i - 1][cap]) {
            // Item i-1 dipilih
            chosen.push_back(i - 1);
            cap -= w[i - 1];
        }
    }
    std::cout << "Item yang dipilih (indeks): ";
    for (int idx : chosen) std::cout << idx << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Nilai maksimum = 10
Item yang dipilih (indeks): 3 1

Baris if (dp[i][cap] != dp[i - 1][cap]): bila dp[i][cap] berbeda dari dp[i-1][cap], artinya item i-1 ikut dipilih (opsi ambil dipakai).
Baris cap -= w[i - 1];: kurangi kapasitas dengan bobot item yang dipilih, lanjutkan traceback.
Hasil indeks {3, 1}: item ke-3 (bobot 5, nilai 6) dan ke-1 (bobot 3, nilai 4). Total bobot 8, nilai 10. Cocok dengan solusi optimal.

Tabel Kompleksitas #

Versi	Dimensi DP	Waktu	Ruang	Catatan
0/1 knapsack 2D	`(n+1) × (W+1)`	`O(n·W)`	`O(n·W)`	Mudah untuk traceback
0/1 knapsack 1D	`W+1`	`O(n·W)`	`O(W)`	Loop mundur
Unbounded knapsack	`W+1`	`O(n·W)`	`O(W)`	Loop maju
Fractional knapsack	Sort + greedy	`O(n log n)`	`O(1)`	Bukan DP, pakai greedy

Aplikasi dan Variasi #

Subset sum: “apakah ada subset dengan total = K?” — knapsack dengan v[i] = w[i], target W = K, cek dp[n][K] == K.
Partition equal subset sum: belah array menjadi dua subset dengan total sama. Setara dengan subset sum target sum/2.
Target sum: tambah/kurangi elemen untuk mencapai target. Bisa direduksi ke subset sum.

Ringkasan #

0/1 knapsack: state dp[i][cap], transisi max(lewat, ambil). Kompleksitas O(n·W).
Optimasi ruang 1D: loop kapasitas mundur agar item tidak dipakai dua kali.
Unbounded knapsack: loop kapasitas maju, item boleh dipakai berulang.
Traceback: bandingkan dp[i][cap] dengan dp[i-1][cap]. Bila berbeda, item dipilih.
Variasi: subset sum, partition equal subset sum, target sum — semua reducible ke knapsack.