ALGORITMA UNTUK MASALAH KNAPSACK MULTIDIMENSI

Abstract

Knapsack adalah jenis masalah yang populer di bidang kombinatorial dan optimasi. Masalah knapsack adalah bagaimana memilih objek yang akan dimasukkan ke dalam knapsack sehingga  kendala terpenuhi dan memperoleh keuntungan maksimum. Knapsack sederhana hanya memiliki satu kendala, sedangkan knapsack multidimensional memiliki lebih dari 1 kendala. Semakin banyak kendala maka semakin susah diselesaikan. Masalah ini termasuk ke dalam kelas NP-hard sehingga membutuhkan algoritma heuristik untuk menemukan solusinya. Pendekatan greedy digunakan untuk mengaproksimasi solusi dengan efisien. Konsep greedy yang digunakan adalah dengan memasukkan objek ke dalam knapsack berdasarkan urutan efisiensinya. Pada penelitian ini dibandingkan beberapa jenis efisiensi yang dapat memberikan solusi yang lebih baik. Untuk pengujian digunakan beberapa data dari benchmark masalah knapsack dengan ukuran n hingga 2500 dan ukuran m hingga 100.

Kata Kunci: Greedy, Heuristik, Knapsack Multidimensi.