Penyelesaian Integer Knapsack Problem Menggunakan Algoritma Greedy, Dynamic Programming, Brute Force dan Genetic

Integer knapsack problem adalah masalah yang ada pada riset operasi di bab program bilangan bulat, dimana bertujuan untuk memaksimalkan total nilai barang ke tempat yang diinginkan dengan memiliki batasan tertentu. Keputusannya ada 2 yaitu 1 (diambil) dan 0 (tidak diambil). Data yang digunakan untuk input merupakan data hasil wawancara dengan J&T Express drop point Ngaliyan, dan penelitian ini terbagi menjadi beberapa penjelasan yaitu (1) Integer knapsack problem, (2) Penyelesaian integer knapsack problem menggunakan algoritma greedy, dynamic programming, brute force, genetic dan implementasi keempat algoritma tersebut pada software MATLAB v2017a berbasis GUI, (3) Membandingkan keempat algoritma dalam hal solusi dan waktu komputasi yang optimal. Hasil penelitian ini menghasilkan kesimpulan bahwa algoritma yang efektif dan efisien digunakan untuk data skala kecil ataupun besar adalah algoritma dynamic programming. Penelitian ini juga dapat memberikan wawasan tentang penyelesaian alternatif untuk memecahkan integer knapsack problem.ABSTRACTInteger knapsack problem is a problem that exists in operating research in integer program chapters, which aims to maximize the total value of goods to the desired place by having certain limitations. The decision is 2, namely 1 (taken) and 0 (not taken). The data used for input is data from interviews with J&T Express drop point Ngaliyan and this research is divided into several explanations, namely (1) Integer knapsack problem, (2) Completion of integer knapsack problems using greedy algorithms, dynamic programming, brute force, genetics and implementation of these four algorithms in GUI based MATLAB v2017a software, (3) Comparing the four algorithms in terms of solutions and optimal computing time. The results of this study conclude that an effective and efficient algorithm used for small or large scale data is a dynamic programming algorithm. This study can also provide insight into alternative solutions to solve integer knapsack problems.