Optimization Story: Menyelesaikan Knapsack Problem

Misalkan kita ingin bepergian dengan suatu tas ransel yang tentunya memiliki keterbatasan. Kita ingin bawa laptop, kamera, baju, celana, jaket favorit, snack, chargers, dan buku tapi tidak muat semuanya. Kita harus memilih barang mana saja yang paling worth it untuk dimasukkan ke dalam ransel tersebut.

Nah, dalam dunia matematika dan ilmu komputer, situasi ini dikenal sebagai Knapsack Problem.

Latar Belakang: Dari Perjalanan sampai ke Algoritma

Knapsack Problem bukan cuma teori random. Problem ini pertama kali diformalkan oleh matematikawan pada abad ke-19, tapi konsepnya sudah ada sejak orang mulai memikirkan cara mengemas barang dengan efisien. Istilah “knapsack” sendiri berasal dari bahasa Jerman untuk “ransel”.

Hal yang membuat masalah ini menarik adalah kesederhanaannya tapi powerful.

Kita hanya cuma punya satu tas dengan kapasitas terbatas, dan beberapa barang dengan berat dan nilai yang berbeda. Tujuannya? Memilih kombinasi barang yang nilainya maksimal, tanpa melebihi kapasitas tas.

Masalah Klasik yang Wajib Diketahui

Tidak berlebihan kalau dibilang knapsack problem adalah “hello world” -nya optimisasi. Siapa pun yang baru belajar optimalisasi, baik di kampus, bootcamp, atau otodidak pasti akan bertemu dengan problem ini. Alasannya?

1. Simpel tapi challenging.
   • Formulasinya mudah dipahami, tapi solving-nya tidak trivial (bahkan termasuk NP-hard!).
2. Relevan.
   • Aplikasinya mulai dari manajemen inventori, financial portfolio, resource allocation, sampai ke pengaturan bandwidth di jaringan.
   • Saya pernah menuliskan hal yang serupa, yakni bagaimana memilih portofolio diskon produk di e-commerce beberapa tahun lalu.
3. Dasar teknik algoritma.
   • Melalui problem ini, kita bisa belajar konsep greedy method, dynamic programming, dan lainnya.

Jadi, kalau kita mau belajar optimisasi, memahami knapsack problem menjadi suatu kewajiban.

Contoh Problem

Misalkan ada 50 buah items dengan bobot dan values masing-masing. Dari 50 items tersebut, kita akan memilih sebanyak-banyak items yang bisa masuk ke container dengan batasan total bobot item terpilih sebesar 850.

Misalkan berikut ini adalah datanya:

item	values	weights
Item ke-1	360	7
Item ke-2	83	0
Item ke-3	59	30
Item ke-4	130	22
Item ke-5	431	80
Item ke-6	67	94
Item ke-7	230	11
Item ke-8	52	81
Item ke-9	93	70
Item ke-10	125	64
Item ke-11	670	59
Item ke-12	892	18
Item ke-13	600	0
Item ke-14	38	36
Item ke-15	48	3
Item ke-16	147	8
Item ke-17	78	15
Item ke-18	256	42
Item ke-19	63	9
Item ke-20	17	0
Item ke-21	120	42
Item ke-22	164	47
Item ke-23	432	52
Item ke-24	35	32
Item ke-25	92	26
Item ke-26	110	48
Item ke-27	22	55
Item ke-28	42	6
Item ke-29	50	29
Item ke-30	323	84
Item ke-31	514	2
Item ke-32	28	4
Item ke-33	87	18
Item ke-34	73	56
Item ke-35	78	7
Item ke-36	15	29
Item ke-37	26	93
Item ke-38	78	44
Item ke-39	210	71
Item ke-40	36	3
Item ke-41	85	86
Item ke-42	189	66
Item ke-43	274	31
Item ke-44	43	65
Item ke-45	33	0
Item ke-46	10	79
Item ke-47	19	20
Item ke-48	389	65
Item ke-49	276	52
Item ke-50	312	13

Mathematical modelling-nya adalah sebagai berikut:

Decision variables didefinisikan sebagai merupakan binary variable. Jika produk ke i terpilih ke container, maka nilainya 1. Sedangkan jika produk tersebut tidak terpilih, maka nilainya 0.

Constraints-nya total semua bobot item terpilih tak boleh melebihi

1. Bisa dituliskan sebagai berikut: .

Objective function-nya adalah memaksimalkan total values dari item terpilih. Bisa dituliskan sebagai berikut: .

Jika dituliskan dalam skrip R dengan library(ompr):

capacity = 850
n        = length(values)

# Membuat model knapsack
model =
  MIPModel() %>%
  # Variabel biner: 1 jika item dipilih, 0 jika tidak
  add_variable(x[i], i = 1:n, type = "binary") %>%
  # Fungsi objektif: maksimalkan total value
  set_objective(sum_expr(values[i] * x[i], i = 1:n), "max") %>%
  # Constraint: total weight tidak boleh melebihi kapasitas
  add_constraint(sum_expr(weights[i] * x[i], i = 1:n) <= capacity)

# Menyelesaikan model
solution =
  model %>% 
  solve_model(with_ROI(solver = "glpk"))

# Mengekstrak hasil
total_value    = solution$objective_value
selected_items = which(solution$solution[1:n] > 0.5)  # Ambil item dengan nilai > 0.5
packed_weights = weights[selected_items]
total_weight   = sum(packed_weights)

Berikut adalah solusi yang dihasilkan:

Total value = 7534 

Total weight: 850 

Packed items: 1 2 4 5 7 11 12 13 15 16 17 18 19 20 22 23 25 28 29 30 31 32 33 35 39 40 42 43 45 48 49 50 

Packed weights: 7 0 22 80 11 59 18 0 3 8 15 42 9 0 47 52 26 6 29 84 2 4 18 7 71 3 66 31 0 65 52 13 

Ini adalah hasilnya dalam bentuk tabel:

[1] "Detailed results:"

Item	Value	Weight
1	360	7
2	83	0
4	130	22
5	431	80
7	230	11
11	670	59
12	892	18
13	600	0
15	48	3
16	147	8
17	78	15
18	256	42
19	63	9
20	17	0
22	164	47
23	432	52
25	92	26
28	42	6
29	50	29
30	323	84
31	514	2
32	28	4
33	87	18
35	78	7
39	210	71
40	36	3
42	189	66
43	274	31
45	33	0
48	389	65
49	276	52
50	312	13
Total	7534	850

Conclusion

Secara pemodelan matematika, membangun model dari knapsack problem cukup mudah karena hanya memiliki satu constraint dan satu objective function saja.

---

if you find this article helpful, support this blog by clicking the ads.