Pada kesempatan kali ini saya akan menjelaskan tentang Knapsack Problem.
Knapsack Problem
Salah satu
penggunaan metode greedy adalah untuk menyelesaiakan permasalahan Knapsack
(Knapsack problem), knapsack problem bisa kita gambarkan, misalnya kita
mempunyai sebuah kantong atau tas dengan kapasitas tertentu sedangkan dihadapan
kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana
saja yang kira-kira akan kita angkut sesuai kapasitas kantong yang kita miliki
supaya kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.
- Greedy by Profit
Strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang atau objek dengan nilai keuntungan terbesar terlebih dahulu ke dalam kantong atau knapsack. Jadi strategi ini hanya mempertimbangkan jumlah keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa tidak melebihi kapasitas kantong yang kita miliki. - Greedy by weight
Pada strategi ini, kita berusaha memasukan barang sebanyak-banyaknya kedalam kantong, jadi barang atau objek yang dimasukan terlebih dahulu adalah barang dengan bobot paling ringan terlebih dahulu, dengan harapan dengan banyaknya barang atau objek yang terangkut kita bisa mendapatkan keuntungan sebesar-besarnya. - Greedy by density
Strategi ini mengharapkan keuntungan sbesar-besarnya dengan memasukan barang yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong.
- Masukkan objek satu per satu ke dalam knapsack. Sekali objek dimasukkan ke dalam knapsack, objek tersebut tidak bisa dikeluarkan lagi.
Namun karena
metode greedy hanya mempertimbangkan keuntungan local dengan
harapan mendapat keuntungan global –seperti yang sudah dijelaskan sebelumnya-,
maka metode ini juga tidak menjamin akan memberikan solusi optimal.
Contoh 1 :
N = 4; Maksimum kapasitas = 20 kg
W1 = 20 kg P1 = 120
W2 = 10 kg P2 = 80
W3 = 5 kg P3 = 50
W4 = 10 kg P4 = 70
Kesimpulan nya adalah dengan menggunakan metode greedy tidaklah selalu mendapatkan hasil yang optimal.
Source :
http://bloglogika.blogspot.co.id/2011/01/knapsack-problem.html
Tidak ada komentar:
Posting Komentar