PENERAPAN ALGORITMA DYNAMIC PROGRAMMING DAN ALGORITMA BACKTRACKING PADA PERMASALAHAN MULTIPLE CONSTRAINTS KNAPSACK 0-1

Abstract

Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian banyak objek dengan batasan objek tersebut sama atau lebih kecil dari kapasitas media penyimpannya sehingga diperoleh suatu penyimpanan yang optimal. Knapsack dapat diilustrasikan sebagai suatu kantong atau media penyimpanan. Perkembangan teknologi saat ini memungkinkan pencarian solusi optimal tersebut dilakukan oleh aplikasi komputer karena keterbatasan manusia untuk menyelesaikan masalah knapsack. Masalah knapsack dapat dilakukan dengan berbagai macam algoritma, diantaranya adalah menggunakan algoritma Dynamic Programming dan algoritma Backtracking. Tujuan penelitian ini adalah untuk menyelesaikan masalah Multiple Constraints Knapsack Problem (MCKP) 0-1 menggunakan algoritma Dynamic Programming dan algoritma Backtracking dan membandingkan kedua algoritma tersebut. Penelitian ini dilakukan di industri Usaha Dagang (UD) Indo Handicraft yang terletak di Jalan Raya Tamanan, Desa Grujugan Kidul, Kecamatan Grujugan, Kabupaten Bondowoso. Pengambilan data dilakukan dengan metode wawancara dan data yang diambil berupa data harga beli per paket, harga jual per paket, dan berat barang per paket. Untuk menerapkan data tersebut dilakukan pengidentifikasian untuk mencari keuntungan (𝑝𝑗 ). Tujuan dari peneliti adalah untuk mencari keuntungan maksimum di UD Indo Handicraft pada permasalahan Multiple Constraints Knapsack Problem (MCKP) 0-1 menggunakan algoritma Dynamic Programming dan algoritma Backtracking. Berdasarkan hasil dan pembahasan menunjukkan bahwa setelah dilakukan pemilihan barang yang dibeli oleh UD Indo Handicraft, didapatkan keuntungan maksimum menggunakan algoritma Dynamic Programming adalah sebesar Rp. 2.238.000,- dengan berat maksimum 228 kg dan modal maksimum Rp. 6.578.000,- dengan waktu proses 29,2586 detik. Pada algoritma Backtracking diperoleh keuntungan maksimum sebesar Rp. 2.238.000,- dengan berat maksimum 228 kg dan modal maksimum Rp. 6.578.000,- dengan waktu proses 1119,8306 detik. Dari hasil kedua algoritma di atas dapat disimpulkan bahwa algoritma Dynamic Programming dan algortima Backtracking menghasilkan keuntungan yang sama, tetapi dalam segi lama waktu program dijalankan (running time), algoritma Dynamic Programming membutuhkan waktu yang lebih singkat daripada algoritma Backtracking. Dengan kata lain, algoritma Dynamic Programming lebih efektif dan efisien untuk menyelesaikan permasalahan Multiple Constraints Knapsack 0-1.