Penyelesaian Knapsack Problem dengan Kriteria Greedy

Algoritma Greedy merupakan metode yang digunakan dalam suatu penyelesaian masalah optimasi yang diselesaikan secara bertahap (step by step), dengan harapan hasil yang didapatkan merupakan hasil terbaik yang dapat diperoleh (Kurniasari, 2006). Algoritma Greedy melibatkan pencarian sebuah himpunan bagian kandidat yang harus memenuhi beberapa kriteria yang ditentukan yaitu menyatakan suatu solusi dan optimasi dari suatu objek (Jakaria dan Rosid, 2017). Tujuan dari Greedy Algorithm adalah mencari solusi yang mendekati nilai optimal dengan memaksimumkan atau meminimumkan hasil penyelesaian yang didapat. Penggunaan metode Greedy untuk pencarian lintasan terpendek sangat berguna untuk menentukan kemungkinan jalan tersingkat untuk menuju suatu tempat tujuan (Hayati, E.N. & Yohanes, 2014).

Knapsack berasal dari bahasa inggris yang berarti ransel atau karung. Knapsack Problem merupakan suatu metode yang dapat digunakan untuk memecahkan permasalahan dalam pemilihan barang secara tepat, dimana berat dan keuntungan dari setiap barang berbeda-beda. Tujuan dari Knapsack adalah untuk mendapatkan keuntungan yang maksimal dari pemilihan barang yang tepat. Strategi yang digunakan dalam penyelesaian Knapsack Problem ini adalah semua objek (benda) dimasukkan satu per satu dan objek yang sudah berada di dalam ransel tidak dapat dikeluarkan lagi. Strategi yang dapat digunakan untuk memasukkan objek ke dalam ransel/knapsack (Silvano et al., 1990) adalah sebagai berikut :