Penyelesaian Masalah Knapsack (0-1) Menggunakan Algoritma Greedy

Abstract

Seiring dengan berkembangnya zaman serta kemajuan teknologi dan informasi seperti halnya pada bidang jasa proses pengiriman barang di Indonesia sedang meningkat dikarenakan sangat membantu serta hemat waktu dan tenaga. Jasa pengiriman barang ingin mendapatkan keuntungan yang lebih besar dan juga konsumen tidak merasa terbebani oleh biaya yang besar, maka dari itu harus saling menguntungkan satu sama lain. Paket pengiriman yang paling populer dan paling digemari oleh konsumen ialah paket reguler yang disebabkan oleh faktor biaya yang murah, layanannya sangat cepat dengan memakan waktu 3-4 hari. paket reguler ini sangat cocok digunakan untuk kasus masalah knapsack. Knapsack dapat diartikan sebagai karung atau kantung yang digunakan untuk menyimpan sesuatu. Tentu tidak semua objek dapat ditampung di dalam karung. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung. Rumusan masalah dalam penelitian ini adalah: 1) Bagaimana penyelesaian masalah integer knapsack menggunakan algoritma greedy; dan 2) Bagaimana algoritma greedy memberikan solusi optimal untuk permasalahan integer knapsack. Adapun tujuan dari penelitian ini adalah: 1) Mengetahui penyelesaian pada permasalahan integer knapsack problem menggunakan algoritma greedy; dan 2) Mengetahui hasil solusi optimal pada algoritma greedy dalam penyelesaian integer knapsack problem. Dari hasil akhir perhitungan dapat disimpulkan bahwa total berat dan total keuntungan menggunakan algoritma greedy solusi yang paling optimal ialah dengan total bobot sebesar 41 dan total keuntungan 90.

Along with the development of the times and advances in technology and information as well as in the field of goods delivery services in Indonesia is increasing because it is very helpful and saves time and energy. Goods delivery services want to get a bigger profit and also consumers do not feel burdened by large costs, therefore should benefit each other. The most popular and most popular delivery package by consumers is the regular package due to the low-cost factor, the service is very fast with 3-4 days. This regular package is perfect for knapsack problem cases. A knapsack can be interpreted as a sack or pouch used to store something. Of course, not all objects can be accommodated in a sack. The sack can only store a few objects with a total size (weight) smaller or equal to the size of the sack capacity. The formulation of the problems in this study is 1) How to solve the problem of knapsack integers using greedy algorithms, and 2) How greedy algorithms provide the optimal solution to knapsack integer problems. The objectives of this study are: 1) Knowing the solution to the problem of integer knapsack problem using a greedy algorithm, and 2) Know the optimal solution results on greedy algorithms in solving the integer knapsack problem. From the final result of the calculation can be concluded that the total weight and total profit using greedy algorithm the most optimal solution is with a total weight of 41 and a total profit of 90.