Perbandingan Metode Branch and Bound dan Enumerasi implisit dalam menyelesaikan masalah Knapsack

Fakhry Asad Agusfrianto (Universitas Negeri Jakarta)
Ramya Rachmawati

AKSIOMA
Vol 13, No 1 (2022): AKSIOMA: Jurnal Matematika dan Pendidikan Matematika

Masalah knapsack merupakan masalah program bilangan bulat yang melibatkan satu kendala saja. Masalah knapsack umumnya diilustrasikan dengan suatu tas dan barang. Masalah yang akan kita selesaikan dalam masalah knapsack adalah memaksimumkan harga barang dengan kapasitas tertentu yang dapat dimuat oleh tas dengan kapasitas tertentu juga. Dalam menyelesaikan masalah knapsack, umumnya dapat dikerjakan secara langsung (penerkaan), menggunakan metode branch and bound, dan enumerasi implisit. Pada paper ini, akan dilakukan perbandingan penyelesaian masalah knapsack dengan metode branch and bound dan enumerasi implisit. Kita juga akan dapat melihat metode mana yang paling efektif untuk menyelesaikan suatu masalah knapsack.