Pencarian K solusi terbaik untuk permasalahan 0/1 knapsack dengan algoritma branch and bound

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.