Abstract:
Permasalahan knapsack (knapsack problem) merupakan permasalahan untuk mencari kombinasi
item-item yang memiliki berat (w1,w2, ...wn) dan nilai (v1, v2, ...vn) sehingga dapat dimasukkan
ke dalam sebuah tas dengan kapasitas C. Kombinasi yang dipilih haruslah kombinasi yang paling
berharga yang cukup untuk masuk ke dalam knapsack. Dengan kata lain tujuan penyelesaian
permasalahan knapsack adalah untuk mencari kombinasi item-item yang total beratnya tidak
melebihi kapasitas knapsack dan memiliki nilai tertinggi.
Selain itu solusi yang dicari tidak hanya berupa 1 solusi saja tetapi beberapa solusi terbaik (k
best solution). Untuk menyelesaikan permasalahan ini pendekatan yang paling mudah dengan
menggunakan algoritma exhaustive search. Meskipun algoritma ini dapat memberikan solusi
yang terbaik, kompleksitas waktunya terlalu besar (O(2n)) sehingga tidak cocok digunakan
untuk menyelesaikan masalah dengan jumlah objek yang sangat banyak, karena itu dalam skripsi
ini akan digunakan pendekatan metode branch and boundyang diharapkan dapat mempercepat
proses pencarian.
Untuk algoritma branch and bound diimplementasikan secara langsung dari langkah algoritma
tersebut dengan sedikit modifikasi dan digunakan algoritma exhaustive search menggunakan
bit-string sebagai algoritma pembanding.
Berdasarkan hasil pengujian algoritma exhaustive search dan branch and bound, algoritma branch
and bound lebih baik daripada algoritma exhaustive search untuk kasus dengan jumlah item yang
cukup banyak, sedangkan algoritma exhaustive search lebih baik untuk kasus dengan jumlah
item yang terbilang sedikit.
