Penyelesaian Knapsack dengan Algoritma BFS

Penyelesaian Knapsack dengan BFS

Soal diatas dengan tas berkapasitas 10 kg. 5 barang (berat, nilai):

1. Barang 1: (6 kg, 30)
2. Barang 2: (3 kg, 14)
3. Barang 3: (4 kg, 16)
4. Barang 4: (2 kg, 9)
5. Barang 5: (5 kg, 20)

Tujuan: pilih kombinasi barang (masing-masing diambil atau tidak — 0/1 knapsack) sehingga total berat ≤ 10 kg dan total nilai maksimal.

1. Pendekatan dengan BFS

Representasi node:

level = berapa item yang sudah diputuskan (0..n). Jika level == n → daun (semua keputusan selesai).

weight = total berat sampai node ini.

value = total nilai sampai node ini.

chosen = daftar indeks item yang dipilih sampai node ini.

Transisi dari node pada level = i:

Anak 1 (exclude item i+1): level+1, same weight/value, same chosen.

Anak 2 (include item i+1): level+1, weight + w[i], value + v[i], chosen + [i+1].

Varian yang disarankan: BFS dengan pruning berat — saat membuat anak include, hanya enqueu jika weight + w[i] ≤ capacity. Dengan pruning ini kita mengurangi jumlah node yang harus diperiksa (tetap eksponensial tapi lebih kecil).

BFS memastikan kita menjelajah level demi level. Kita memeriksa semua kombinasi (daun) yang mungkin, dan menyimpan solusi terbaik yang feasible.

Pseudocode

FUNCTION BFS_KNAPSACK(items, capacity):
    # items: list of (weight, value), 0-based index
    n = length(items)
    best_value = 0
    best_set = []
    queue = empty queue
    enqueue (level = 0, chosen = [], weight = 0, value = 0)

    WHILE queue not empty:
        (level, chosen, weight, value) = dequeue(queue)

        IF level == n:
            # leaf: semua keputusan sudah dibuat
            IF weight <= capacity AND value > best_value:
                best_value = value
                best_set = chosen.copy()
            CONTINUE

        # 1) child: exclude current item
        enqueue(queue, (level+1, chosen.copy(), weight, value))

        # 2) child: include current item (prune jika berat melebihi kapasitas)
        w2 = weight + items[level].weight
        v2 = value + items[level].value
        IF w2 <= capacity:
            enqueue(queue, (level+1, chosen + [level+1], w2, v2))

    RETURN best_value, best_set
END FUNCTION

Catatan: jika tidak memakai pruning, tetap enqueu anak include walau w2 > capacity, tetapi hanya menerima solusi di daun yang weight ≤ capacity. Pruning menghemat memori dan waktu.

3. Simulasi

Saya tampilkan semua daun (semua kombinasi 5-bit) dalam urutan BFS (level-order). Format: (nomor daun) decisions(0/1) → [daftar item], berat, nilai — feasible?

1. 00000 → [] , berat=0 , nilai=0 — feasible
2. 00001 → [5], berat=5 , nilai=20 — feasible
3. 00010 → [4], berat=2 , nilai=9 — feasible
4. 00011 → [4,5], berat=7 , nilai=29 — feasible
5. 00100 → [3], berat=4 , nilai=16 — feasible
6. 00101 → [3,5], berat=9 , nilai=36 — feasible
7. 00110 → [3,4], berat=6 , nilai=25 — feasible
8. 00111 → [3,4,5], berat=11 , nilai=45 — infeasible (berat>10)
9. 01000 → [2], berat=3 , nilai=14 — feasible
10. 01001 → [2,5], berat=8 , nilai=34 — feasible
11. 01010 → [2,4], berat=5 , nilai=23 — feasible
12. 01011 → [2,4,5], berat=10 , nilai=43 — feasible
13. 01100 → [2,3], berat=7 , nilai=30 — feasible
14. 01101 → [2,3,5], berat=12 , nilai=50 — infeasible
15. 01110 → [2,3,4], berat=9 , nilai=39 — feasible
16. 01111 → [2,3,4,5], berat=14 , nilai=59 — infeasible
17. 10000 → [1], berat=6 , nilai=30 — feasible
18. 10001 → [1,5], berat=11 , nilai=50 — infeasible
19. 10010 → [1,4], berat=8 , nilai=39 — feasible
20. 10011 → [1,4,5], berat=13 , nilai=59 — infeasible
21. 10100 → [1,3], berat=10 , nilai=46 — feasible ← nilai tertinggi sampai titik ini
22. 10101 → [1,3,5], berat=15 , nilai=66 — infeasible
23. 10110 → [1,3,4], berat=12 , nilai=55 — infeasible
24. 10111 → [1,3,4,5], berat=17 , nilai=75 — infeasible
25. 11000 → [1,2], berat=9 , nilai=44 — feasible
26. 11001 → [1,2,5], berat=14 , nilai=64 — infeasible
27. 11010 → [1,2,4], berat=11 , nilai=53 — infeasible
28. 11011 → [1,2,4,5], berat=16 , nilai=73 — infeasible
29. 11100 → [1,2,3], berat=13 , nilai=60 — infeasible
30. 11101 → [1,2,3,5], berat=18 , nilai=80 — infeasible
31. 11110 → [1,2,3,4], berat=15 , nilai=69 — infeasible
32. 11111 → [1,2,3,4,5], berat=20 , nilai=89 — infeasible

Komentar pada trace: dari daun-daun feasible, nilai terbaik yang ditemukan oleh BFS (dengan pruning) adalah pada daun nomor 21 (10100) → memilih item 1 dan 3.

4. Hasil akhir

Pilih: Barang 1 dan Barang 3.

1. Berat total = 6 + 4 = 10 kg. (langkah aritmetika: 6 + 4 = 10)
2. Nilai total = 30 + 16 = 46. (langkah aritmetika: 30 + 16 = 46)

Nilai maksimal yang dapat diperoleh (dengan kapasitas 10 kg) = 46.

Hasil komputasi lengkap menunjukkan kombinasi lain yang feasible tidak mencapai nilai 46 (mis. [2,4,5] memberi nilai 43; [1,2] memberi 44; dst).

Kompleksitas & Catatan

Kompleksitas waktu (tanpa pruning): O(2^n) (mengeksplor semua subset).

Kompleksitas ruang BFS (tanpa pruning): O(2^n) (frontier bisa besar).

Dengan pruning berat (tidak menambah child include bila berat melampaui kapasitas), jumlah node yang dikunjungi berkurang (pada contoh ini: dari 63 node total pada pohon lengkap turun menjadi 43 node yang diekspansi — angka ini tergantung data).

Untuk knapsack klasik dengan kapasitas relatif kecil, algoritma Dynamic Programming (pseudo-polynomial O(n·capacity)) biasanya lebih efisien. BFS berguna untuk pemahaman pohon keputusan dan bisa diperluas ke varian yang membutuhkan enumerasi solusi atau constraint tambahan (mis. branch-and-bound / best-first search untuk pruning lebih agresif).

Implementasi Java

from collections import deque

items = [(6,30),(3,14),(4,16),(2,9),(5,20)]  # (berat, nilai)
capacity = 10

def bfs_knapsack(items, capacity):
    n = len(items)
    best_value = -1
    best_set = []
    q = deque()
    q.append((0, [], 0, 0))  # level, chosen(list of 1-based indices), weight, value
    nodes_expanded = 0

    while q:
        level, chosen, w, v = q.popleft()
        nodes_expanded += 1

        if level == n:
            if w <= capacity and v > best_value:
                best_value = v
                best_set = chosen.copy()
            continue

        # exclude next item
        q.append((level+1, chosen.copy(), w, v))

        # include next item (prune bila berat melebihi kapasitas)
        w2 = w + items[level][0]
        v2 = v + items[level][1]
        if w2 <= capacity:
            q.append((level+1, chosen + [level+1], w2, v2))

    return best_value, best_set, nodes_expanded

best_value, best_set, nodes_expanded = bfs_knapsack(items, capacity)
print("Best value:", best_value)
print("Best set (item indices):", best_set)
print("Nodes expanded:", nodes_expanded)

Perkiraan output:

Best value: 46
Best set (item indices): [1, 3]
Nodes expanded: (nilai tergantung implementasi; pada contoh ini ~43)

Kesimpulan

BFS (dengan pruning berat) berhasil menemukan solusi optimal: Barang 1 + Barang 3, nilai total 46, berat total 10 kg.

BFS mudah dimodelkan sebagai traversa pohon keputusan tetapi tidak efisien untuk n besar — untuk kasus knapsack standar biasanya lebih baik menggunakan Dynamic Programming atau Branch-and-Bound.