Knapsack Problem: Contoh Kasus Fractional Knapsack Algoritma Greddy
"Pengertian Knapsack Problem, metode penyelesaian masalah contoh kasus Fractional Knapsack Algoritma Greddy,"
57 min read
Pengertian Knapsack Problem
Apa itu Knapsack problem?
 |
| Knapsack Problem |
Knapsack bisa dianalogikan sebagai karung atau tas yang memiliki kapasitas tertentu sebagai tempat menyimpan barang belanjaan. Namun tidak semua barang tersebut dapat dimasukkan ke dalam tas karena kapasitasnya terbatas.
Di sinilah muncul Knapsack problem, yaitu menentukan barang yang paling menguntungkan yang dapat diangkut ke dalam Snapsack. Karena itulah, dibutuhkan algoritma yang dapat memberikan solusi optimal dari Snapsack probelm.
Tujuan dari algoritma penyelesaian masalah Knapsack adalah bagaimana memilih barang yang paling menguntungkan untuk dimasukkan ke dalam tas atau karung yang terbatas itu.
Adapun variasi dan kriteria permasalahan dalam Knapsack problem meliputi:
- 0/1 Knapsak problem, yaitu setiap jenis barang hanya ada 1 unit. Ambil atau lepaskan (Take it or leave it).
- Fractional Knapsack problem, yaitu hanya boleh membawa sebagian barang yang terdiri dari unit dalam pecahan. Contohnya barang seperti gula, tepung dan lain-lain.
- Bounded Knapsack problem: Setiap barang terbatas jumlahnya (Sebanyak N unit).
- Unbounded Knapsack problem, yaitu setiap barang tersedia lebih dari satu unit yang tidak terbatas jumlahnya.
Untuk menentukan prioritas yang paling menguntungkan, kita bisa menggunakan algoritma Greddy. Algoritma Greddy adalah salah satu algoritma yang populer digunakan untuk menyelesaikan kasus optimasi yang berhubungan dengan Knapsack problem.
Algoritma Greddy
Masalah Knapsack dapat diselesaikan dengan metode algoritma Greddy. Terdapat 3 jenis strategi dalam menyelesaikan kasus Snapsack menggunakan algoritma Greddy.
Strategi penentuan barang tersebut dipilih berdasarkan tujuan yang ingin dicapai. Dalam penggunaan algoritam Greddy, yang paling penting diperhatikan adalah memasukkan barang satu per satu ke dalam Snapsack di mana barang yang sudah dimasukkan tidak dapat dikeluarkan kembali.
1. Greddy by profit
Strategi pengangkutan barang dengan algoritma Greddy by profit bertujuan untuk mendapatkan keuntungan maksimal dari Snapsack.
Pertimbangan terbesar dalam strategi ini adalah jumlah keuntungan semaksimal mungkin dari nilai barang. Namun tetap memperhatikan kapasitas Snapsack dari segi berat barang agar tidak melebihi kapasitas.
2. Greddy by weight
Strategi Greddy by weight bertujuan untuk memaksimalkan barang yang bisa diangkut. Prosesnya dimulai dengan memasukkan barang dengan bobot yang paling ringan terlebih dahulu.
Dengan banyaknya barang yang bisa diangkut ke dalam Snapsack, diharapkan keuntungan maksimal bisa diperoleh.
3. Greddy by density
Strategi Greddy by density digunakan untuk memilih barang yang paling menguntungkan untuk dimasukkan ke dalam Snapsack dengan kualifikasi mendahulukan memasukkan barang yang memiliki keuntungan per unit terbesar.
Secara umum, metode Greddy hanya mempertimbangkan keuntungan lokal dengan harapan dapat memperoleh keuntungan global. Karena itulah, strategi Greddy juga tidak dapat menjamin akan memberikan solusi optimal barang yang harus dimasukkan ke dalam Snapsack.
Knapsack Problem: Contoh Kasus Fractional Knapsack Algoritma Greddy
Permasalahan Knapsack atau yang biasa kita kenal dengan sebutan 0/1 Knapsack merupakan salah satu dari persoalan klasik yang banyak ditemukan pada literatur-literatur lama dan hingga kini permasalahan ini masih banyak ditemukan dalam kehidupan sehari-hari.
Contoh kongkret permasalahan ini dalam dunia nyata adalah penjualan beberapa jenis keperluan rumah tangga oleh pedagang keliling dengan menggunakan gerobak ataupun alat pengangkut lainnya yang hanya memiliki kapasitas angkut maksimum sebesar w kg.
Keperluan rumah tangga yang akan dijual hanya berjumlah satu untuk tiap jenisnya dan tiap jenis barang memiliki berat w1, w2, w3, w4, ...wn dengan keuntungan yang diperoleh untuk tiap jenisnya adalah p1, p2, p3, p4, ..., pn.
Tidak semua jenis keperluan rumah tangga yang akan dijual oleh pedagang keliling tersebut dapat dimasukan kedalam alat pengangkut. Maka akan dipilih jenis-jenis keperluan rumah tangga yang akan dijual untuk setiap harinya oleh pedagang keliling tersebut agar diperoleh keuntungan yang maksimal dari penjualan barang-barang keperluan rumah tangga tersebut.
w1 = 10; p1 = 2
w2 = 5; p2 = 3
w3 = 15; p3 = 5
w4 = 7; p4 = 7
w5 = 6; p5 = 1
w6 = 18; p6 = 4
w7 = 3; p7 = 1
M = 15
1. Metode penyelesaian program 0-1 contoh kasus 0/1 Knapsack problem
1/0 Knapsack M = 15
Properti objek | Greddy by | Solusi Optimal | |||||
i | wi | pi | pi /wi | profit | weight | density | |
1 | 2 | 10 | 5 | 1 | 1 | 1 | 1 |
2 | 3 | 5 | 1,7 | 1 | 1 | 0 | 1 |
3 | 5 | 15 | 3 | 1 | 0 | 1 | 1 |
4 | 7 | 7 | 1 | 0 | 0 | 0 | 0 |
5 | 1 | 6 | 6 | 1 | 1 | 1 | 1 |
6 | 4 | 18 | 4,5 | 1 | 1 | 1 | 1 |
7 | 1 | 3 | 3 | 0 | 1 | 1 | 0 |
Total bobot : | 15 | 11 | 13 | 15 | |||
Total keuntungan : | 54 | 42 | 52 | 54 | |||
Kesimpulan: Pada soal ini, algoritma Greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkan weight dan density tidak memberikan solusi optimal.
2. Metode penyelesaian masalah contoh kasus Fractional Knapscak
Fractional Knapscak M = 15
Properti objek | Greddy by | |||||
i | wi | pi | pi /wi | profit | weight | density |
1 | 2 | 10 | 5 | 1 | 1 | 1 |
2 | 3 | 5 | 1,7 | 0 | 1 | 2/3 |
3 | 5 | 15 | 3 | 1 | 4/5 | 1 |
4 | 7 | 7 | 1 | 4/7 | 0 | 0 |
5 | 1 | 6 | 6 | 0 | 1 | 1 |
6 | 4 | 18 | 4,5 | 1 | 1 | 1 |
7 | 1 | 3 | 3 | 0 | 1 | 1 |
Total bobot : | 15 | 15 | 15 | |||
Total keuntungan : | 47 | 48 | 55 | |||
Solusi optimal X = (1,2/3,1,0,1,1,1)
Yang memberikan keuntungan maksimum 55
Catatan:
- 1 menandakan barang dimasukan
- 0 menandakan barang tidak dimasukan
- Pada bagian "profit" utamakan memasukan jumlah barang agar mendekati keuntungan maksimal
- Pada bagian "weight" utamakan memasukan jumlah barang agar mendekati beban maksimal
- Pada bagian "density" utamakan memasukan jumlah barang agar mendekati harga keuntungan per-unit barang maksimal.
1. http://rahmamaulana17.blogspot.com/2016/10/knapsack-problem-metode-greddy-soal_13.html
2. http://whitenote03.blogspot.com/2016/10/knapsack-problem.html#widget-themater_tabs-1432447472-id1
Lihat juga Contoh Soal dan Jawaban Metode Branch and Bound (Grafik)
Itulah sedikit materi tentang Knapsack problem, contoh kasus Fractional Knapsack Algoritma Greddy. Semoga bermanfaat!