Perbandingan Penyelesaian Knapsack Problem Secara Matematika, Kriteria Greedy Dan Algoritma Greedy

Deddy Supriadi

Sari


Abstract- Knapsack problem is a problem how to select object from many object sand how weight it will be saved in order to obtain anoptimal storage with consider which consists of n objects(1,2,3, ...) where each objecthas a weight(Wi) and profit(Pi). Further more capacity from storage (M) and probability from each object must be considered. In this paper discuss how to solving knapsack problem with three ways. They are mathematic, greedy criteria and greedy algorithm.  They have different way to solve knapsack problem. After the comparison, more optimized and more easily is greedy criteria. But more difficult and the result are not optimal use mathematic. Greedy algorithm will be effective if it is non decreasing. This method is faster but we must understand before hand about greedy algorithm

Keywords: greedy, knapsack, mathematic, profit, weight

 

Abstrak - Masalah Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian banyak dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu penyimpanan yang optimal dengan memperhatikan objek yang terdiri dari n objek (1,2,3,…) dimana setiap objek memiliki bobot (Wi) dan profit (Pi) dengan memperhatikan juga kapasitas dari media penyimpanan sebesar M dan nilai probabilitas dari setiap objek (Xi).Dalam jurnal ini membahas metode kajian mengenai cara menyelesaikan permasalahan Knapsack ini dengan membandingkan tiga cara, yaitu dengan cara matematika, kriteria greedy, dan dengan algoritma greedy. Masing-masing cara ini memiliki perbedaan dalam penyelesaiannya. Setelah dilakukan perbandingan maka lebih optimal dan lebih mudah dikerjakan yaitu dengan cara kriteria greedy. Sedangkan yang lebih sulit dan hasilnya tidak optimal digunakan secara matematika. Untuk cara algoritma greedy akan efektif apabila disusun secara tidak naik (non descreasing). Cara ini memang lebih cepat akan tetapi kita harus memahami terlebih dahulu tentang algoritma greedy.

Kata Kunci: greedy, knapsack, matematika, profit, bobot

Teks Lengkap:

PDF

Referensi


Dian dan Ade. 2013. Implementasi Algoritma Greddy untuk Menyelesaikan Masalah Knapsack Problem. Jurnal Ilmiah Saintikom. Jurusan Ilmu Komputer Universitas Sumatera Utara. Vol. 12, No. 3, September 2013.

Komang. 2010. Implementasi Algoritma Genetika pada knapsack problem untuk optimasi pemilihan buah kemasan kotak. Seminar Nasional Aplikasi Teknologi Informasi 2010 (SNATI 2010). Yogyakarta, 19 Juni 2010.

Knapsack problem dengan algoritma dan metode greedy by Hendry Prihandono https://hendryprihandono.wordpress.com/2009/01/03/knapsack-problem-dengan-algoritma-dan-metode-greedy/ diunduh (9 Oktober 2016)

Yulikuspartono. 2001. Pengantar Logika dan Algoritma. Yogyakarta: Andi.




DOI: https://doi.org/10.31294/ijcit.v1i2.1835

P-ISSN: 2527-449X E-ISSN: 2549-7421
Statistik Pengunjung Jurnal IJCIT
 

Dipublikasikan oleh LPPM Universitas Bina Sarana Informatika

Jl. Kramat Raya No.98, Kwitang, Kec. Senen, Kota Jakarta Pusat, DKI Jakarta 10450
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License