Secara bahasa, Knapsack problem berarti persoalan terkait ransel atau bisa diartikan lebih lanjut sebagai masalah pengepakan. Knapsack Problem meliputi berbagai masalah dalam pemilihan kombinasi barang (item) dari sekumpulan barang yang akan dimuat dalam suatu wadah dengan kapasitas tertentu. Setiap barang memiliki beban (weight) dan nilai/keuntungan (value/profit) masing-masing yang menjadi pertimbangan dalam proses pemilihan tersebut. Hasil yang diharapkan yaitu didapatnya kombinasi barang dengan keuntungan maksimum tanpa melebihi kapasitas wadah yang tersedia. Oleh karena itu, perlu adanya strategi dalam pemilihan barang agar didapatkan hasil yang optimal.
Terdapat dua jenis knapsack problem yaitu 0/1 Knapsack dan Integer Knapsack
- 0/1 Knapsack problem : jenis knapsack problem dimana hanya terdapat 1 buah dari setiap barang/item yang ada dan tidak bisa diambil fraksinya alias barang tetap utuh. Sehingga pilihannya hanya dua, yaitu dibawa (1) atau tidak dibawa (0).
- Integer Knapsack : jenis knapsack problem dimana setiap jenis barang yang akan dimasukkan bisa lebih dari 1 buah selama jumlah barangnya tersedia dan tidak melebihi kapasitas maksimum wadah.
Knapsack Problem menjadi suatu permasalahan yang sudah tak asing lagi baik dalam dunia industri atau bahkan kehidupan sehari-hari.  Misal dalam jasa pengiriman barang khususnya paket reguler. Keterbatasan jumlah kurir yang tidak sebanding dengan jumlah barang yang akan dikirim membuat pengiriman barang harus dilakukan secara berangsur-angsur sesuai nilai yang lebih besar. Hal ini membutuhkan cara terbaik agar sistem pengiriman paket lebih optimal. Contoh sederhana lainnya yaitu seorang penjual aksesoris anak-anak yang membawa barang jualannya dengan gerobak kecil. Tentu saja gerobak kecil tersebut memiliki batas kapasitas barang/ batas maksimum beban yang dibawa, sehingga penjual hanya bisa menaikkan beberapa dagangannya ke dalam gerobak. Penjual harus bisa memilih barang-barang apa saja yang akan ia bawa dengan pertimbangan beban dan keuntungan yang didapat dari tiap barang jualannya, sehingga profit yang akan ia dapat bisa maksimal.
Salah satu algoritma yang dapat digunakan dalam penyelesaian knapsack problem adalah algoritma pemrograman dinamik (Dynamic Programming). Dynamic Programming merupakan metode pemecahan masalah menggunakan prinsip optimalitas dengan menguraikan solusi menjadi beberapa tahapan (stage) sedemikian sehingga solusinya dapat dipandang dari serangkaian keputusan yang saling berkaitan. Perbedaannya dengan pemrograman linear yaitu banyaknya cara atau langkah untuk mencapai suatu fungsi tujuan, dimana pemrograman linear hanya memiliki satu cara, sedangkan pemrograman dinamik memiliki beberapa cara dalam mencapai fungsi tujuan. Pemrograman dinamik tidak memiliki rumusan yang baku, karena tiap problem membutuhkan perumusan tertentu sesuai dengan situasi yang sifatnya individual.Â
Penerapan Dynamic Programming pada Knapsack Problem
Berikut adalah contoh penyelesaian knapsack problem menggunakan dynamic programming :
Seorang penjual buku akan membawa buku dagangannya menggunakan sebuah tas dengan kapasitas beban maksimum 10 kg. Buku dagangan yang ia miliki ada 5 , yaitu buku A, B, C, D, dan E dengan berat dan keuntungan tiap item sebagai berikut
