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 waktu. Hasil penelitian menunjukkan: adalah 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.