PENERAPAN ALGORITMA GREEDY DAN DYNAMIC PROGRAMMING PADA PERMASALAHAN INTEGER KNAPSACK

Abstract

Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian banyak objek dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu penyimpanan yang optimal. Knapsack dapat diilustrasikan sebagai suatu kantong atau media penyimpanan. Kantong atau media penyimpanan tersebut hanya dapat menyimpan beberapa objek dengan batasan objek tersebut sama atau lebih kecil dari kapasitas media penyimpannya. Terkadang keterbatasan manusia dalam menyelesaikan masalah knapsack tanpa menggunakan alat bantu merupakan salah satu kendala dalam pencarian solusi optimum. Dengan adanya algoritma penyelesaian pada masalah integer knapsack diharapkan dapat membantu dalam proses pemilihan barang. Dengan adanya proses pemilihan barang yang tepat maka dapat membantu mendapatkan keuntungan maksimum. Penelitian ini dilakukan di industri perdagangan UD. BINTANG TANI di Jl. Yos. Sudarso Kecamatan Semboro Kabupaten Jember. Pengambilan data dilakukan dengan metode wawancara dan data yang diambil berupa data harga beli, harga jual, dan banyaknya barang. Untuk menerapkan data tersebut dilakukan pengidentifikasian untuk mencari keuntungan ( ) dan ( ). Algoritma yang digunakan pada permasalahan integer knapsack ini adalah algortima Greedy dan Dynamic Programming. Data penelitian yang digunakan yaitu data sekunder. Tujuan dari peneliti adalah untuk mencari keuntungan maksimum di UD. BINTANG TANI pada permasalahan integer knapsack dengan menggunakan algoritma Greedy dan Dynamic Programming, serta membandingkan algoritma Greedy dan Dynamic Programming pada permasalahan integer knapsack dari segi hasil dan kompleksitas waktu. Hasil penelitian menunjukkan: (1) Keuntungan maksimum penggunaan algoritma Greedy adalah sebesar Rp 687.500,- dengan bobot 479 kg. (2) Keuntungan maksimum penggunaan algoritma Dynamic Programming adalah sebesar Rp 691.500,- dengan bobot 499 kg. (3) Algoritma Greedy dan Dynamic Programming pada kasus permasalahan integer knapsack berdasarkan banyak langkah yang dibutuhkan diperoleh hasil pencarian bahwa pada algoritma Greedy diperlukan proses perbandingan sebanyak kali, maka kompleksitas waktunya adalah ( ). Pada algoritma Dynamic Programming jumlah langkah yang diperlukan untuk mencapai solusi optimal adalah sebanyak , maka kompleksitas waktunya adalah ( ). Sehingga algoritma Dynamic Programming mempuyai jumlah kompleksitas yang lebih besar dibandingkan dengan algoritma Greedy. Dari hasil di atas dapat disimpulkan bahwa dari segi hasil algortima Dynamic Programming lebih mencapai hasil yang maksimum daripada algoritma Greedy tetapi dalam segi kompleksitas waktu algoritma Dynamic Programming mempunyai kompleksitas waktu yang lebih besar daripada algoritma Greedy.