Penyelesaian Knapsack Problem dengan Kriteria Greedy

Penyelesaian Knapsack Problem dengan Kriteria Greedy

Algoritma Greedy merupakan metode yang digunakan dalam suatu penyelesaian masalah optimasi yang diselesaikan secara bertahap (step by step), dengan harapan hasil yang didapatkan merupakan hasil terbaik yang dapat diperoleh (Kurniasari, 2006). Algoritma Greedy melibatkan pencarian sebuah himpunan bagian kandidat yang harus memenuhi beberapa kriteria yang ditentukan yaitu menyatakan suatu solusi dan optimasi dari suatu objek (Jakaria dan Rosid, 2017). Tujuan dari Greedy Algorithm adalah mencari solusi yang mendekati nilai optimal dengan memaksimumkan atau meminimumkan hasil penyelesaian yang didapat. Penggunaan metode Greedy untuk pencarian lintasan terpendek sangat berguna untuk menentukan kemungkinan jalan tersingkat untuk menuju suatu tempat tujuan (Hayati, E.N. & Yohanes, 2014).



Knapsack berasal dari bahasa inggris yang berarti ransel atau karung. Knapsack Problem merupakan suatu metode yang dapat digunakan untuk memecahkan permasalahan dalam pemilihan barang secara tepat, dimana berat dan keuntungan dari setiap barang berbeda-beda. Tujuan dari Knapsack adalah untuk mendapatkan keuntungan yang maksimal dari pemilihan barang yang tepat. Strategi yang digunakan dalam penyelesaian Knapsack Problem ini adalah semua objek (benda) dimasukkan satu per satu dan objek yang sudah berada di dalam ransel tidak dapat dikeluarkan lagi. Strategi yang dapat digunakan untuk memasukkan objek ke dalam ransel/knapsack (Silvano et al., 1990) adalah sebagai berikut :



Penyelesaian Knapsack Problem dengan Kriteria Greedy

    1. Greedy by profit

      Pemilihan objek untuk setiap langkah dilakukan dengan pertimbangan keuntungan terbesar yang akan didapatkan. Tujuan dari strategi ini adalah untuk memaksimumkan keuntungan yang akan didapatkan dengan memprioritaskan pemilihan objek yang paling menguntungkan.

    2. Greedy by weight

      Pemilihan objek untuk setiap langkah dilakukan dengan pertimbangan berat objek terkecil yang dimiliki. Tujuan dari strategi ini adalah untuk memaksimumkan keuntungan yang akan didapatkan dengan cara mencoba untuk memasukkan objek sebanyak-banyaknya ke dalam.

    3. Greedy by density

      Pemilihan objek untuk setiap langkah dilakukan dengan pertimbangan masa jenis dari objek yang terbesar. Tujuan dari strategi ini adalah untuk memaksimumkan keuntungan yang akan didapatkan dengan mencari objek yang dengan keuntungan per unit terbesar.

 

 

 

Pembahasan lainnya :

 

 

 

 






 

Sumber : file:///C:/Users/ASUS/Downloads/309-1-1020-2-10-20190413.pdf

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote count:

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

Originally posted 2023-09-26 23:35:13.

Sistem Informasi