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

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