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

Muhammad Abdurrahman Rois, Siti Maslihah, Budi Cahyono

Abstract


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.


ABSTRACT

Integer 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.

 


Keywords


Integer knapsack problem; Algoritma Greedy; Algoritma Dynamic Programming; Algoritma Brute Force; Algoritma Genetic

Full Text:

PDF (Indonesian)

References


Escobar, F. A., Kolar, A., Harb, N., Vinci Dos Santos, F., & Valderrama, C. (2017). Scalable shared-memory architecture to solve the Knapsack 0/1 problem. Microprocessors and Microsystems, 50, 189–201. https://doi.org/10.1016/j.micpro.2017.04.001

Fanggidae, A., & Lado, F. R. (2015). Algoritma Genetika dan Penerapannya. TEKNOSAIN.

Ghozali, A. E., Setiawan, B. D., & Furqon, M. T. (2017). Aplikasi Perencanaan Wisata di Malang Raya dengan Algoritma Greedy, 1(12), 1459–1467.

Juwita, P. S., Susanto, E., & Halomoan, J. (2017). Perancangan Dan Implementasi Manajemen Daya Listrik Menggunakan Algoritma Greedy Untuk Otomatisasi Rumah. In e-Proceeding of Engineering (Vol. 4, pp. 1512–1519).

Kellerer, Hans, Pferschy, U., & Pisinger, D. (2004). Knapsack Problems. Knapsack Problems. Springer-Verlag Berlin Heidelberg New York. https://doi.org/10.1007/978-3-540-24777-7_9

Kwarteng, A., & Asante, B. (2017). Optimal Advertisement Placement Slot Using Knapsack Problem (A Case Study of Television Advertisement of Tv 3 Ghana). International Journal of Engineering Research and Applications, 07(04), 46–62. https://doi.org/10.9790/9622-0704044662

Levitin, A. (2012). Introduction to The Design & Analysis of Algorithms. Pearson (3rd ed.). PEARSON.

Lin, B., Liu, S., Lin, R., Wu, J., Wang, J., & Liu, C. (2017). Modeling the 0-1 Knapsack Problem in Cargo Flow Adjustment. Symmetry, 9(7), 118. https://doi.org/10.3390/sym9070118

Messac, A. (2015). Optimization in Practice with MATLAB. Book. Cambridge University Press.

Nuraeni. (2016). Jasa Logistik Melesat di Era e-Commerce. Kominfo. Retrieved from kominfo.go.id.index.php/content/detail/6707/Jasa+Logistik+Melesat+di+Era+e-Commerce+/0/sorotan_media

Pan, X., & Zhang, T. (2018). Comparison and Analysis of Algorithms for the 0/1 Knapsack Problem. IOP Journal of Phisics, 1–8. https://doi.org/10.1088/1742-6596/1069/1/012024

Parkinson, A. R., Balling, R., & Hedengren, J. D. (2013). Optimization Methods for Engineering Design. Brigham Young University, 18. https://doi.org/10.1002/9780470686652.eae495

Sampurno, G. I., Sugiharti, E., & Alamsyah. (2018). Comparison of Dynamic Programming Algorithm and Greedy Algorithm on Integer Knapsack Problem in Freight Transportation. Scientific Journal of Informatics, 5(1). Retrieved from http://journal.unnes.ac.id/nju/index.php/sji

Siang, J. J. (2014). Riset Operasi dalam Pendekatan Algoritmis (Edisi 2). ANDI Yogyakarta.

Syarif, A. (2014). Algoritma Genetika; Teori dan Aplikasi (Edisi 2). Yogyakarta: Graha Ilmu.

Tarliah, D. T., & Dimyati, A. (2016). Operations Research Model-Model Pengambilan Keputusan. Bandung: Penerbit Sinar Baru Algensindo.

Zukhri, Z. (2014). ALGORITMA GENETIKA: Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi. Yogyakarta: C.V. ANDI OFFSET.




DOI: http://dx.doi.org/10.35671/telematika.v12i2.841

Refbacks

  • There are currently no refbacks.




Indexed by:


Telematika
ISSN: 2442-4528 (online) | ISSN: 1979-925X (print)
Published by : Universitas Amikom Purwokerto
Jl. Let. Jend. POL SUMARTO Watumas, Purwonegoro - Purwokerto, Indonesia


Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License .