Penyelesaian Knapsack Problem dengan metode Greedy

        Knapsack  adalah  tas  atau  karung  yang  digunakan  untuk  memasukkan  sesuatu, tapi tidak  semua  barang  bisa  ditampung  ke dalam  karung  tersebut. Karung  tersebut  hanya  dapat menyimpan  beberapa  objek  dengan  total  ukurannya  (weight)  lebih  kecil  atau  sama  dengan ukuran kapasitas karung.

        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 ungkut sesuai kapasitas kantong yang kita miliki supaya bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.

Dalam menghadapi masalah seperti di atas, metode greedy memiliki 3 pilihan strategi pengangkutan, yaitu :

1. 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.
2. 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.
3. Greedy by density
   Strategi ini mengharapkan keuntungan sebesar-besarnya dengan memasukan barang yang memiliki keuntungan per-unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong. 

Tata cara yang digunakan metode greedy dalam persoalan knapsack ini adalah :

• Masukkan objek satu per-satu ke dalam knapsack. Sekali objek dimasukkan ke dalam knapsack, objek tersebut tidak bisa dikeluarkan lagi. 

  

Contoh kasus 1:

Tinjau persoalan 0/1 Knapsack dengan 

                        n = 4. 

                        w₁ =   6;    p₁ = 12

                        w₂ =   5;    p₁ = 15

                        w₃ = 10;    p₁ = 50

                        w₄ =   5;    p₁ = 10

                        Kapasitas knapsack W = 16

Solusi dengan algoritma greedy:

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	weight	density
1	6	12	2	0	1	0	0
2	5	15	3	1	1	1	1
3	10	50	5	1	0	1	1
4	5	10	2	0	1	0	0
Total bobot				15	16	15	15
Total keuntungan				65	37	65	65

keterangan :

->  1 = barang dimasukan.
->  0 = barang tidak dimasukan.

->  pada "profit" diutamakan memasukan jumlah barang agar mendekati keuntungan maksimal.

->  pada "weight" diutamakan memasukan jumlah barang agar mendekati beban maksimal.

->  pada "density" diutamakan memasukan jumlah barang agar mendekati harga keuntungan per-unit barang maksimal.

·      Pada contoh diatas, algoritma greedy dengan strategi pemilihan objek berdasarkan profit dan density memberikan solusi optimal, sedangkan pemilihan objek berdasarkan berat tidak memberikan solusi optimal.

Kemudian perhatikan contoh berikut ini 
Contoh kasus 2:

                       persoalan  knapsack lain dengan 6 objek:

            w₁ = 100;  p₁ = 40

                        w₂ = 50;    p₂ = 35

                        w₃ = 45;    p₃ = 18

                        w₄ = 20;    p₄ = 4

            w₅ = 10;    p₅ = 10

                        w₆ = 5;      p₆ = 2

                        Kapasitas knapsack W = 100

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	weight	density
1	100	40	0,4	1	0	0	0
2	50	35	0,7	0	0	1	1
3	45	18	0,4	0	1	0	1
4	20	4	0,2	0	1	1	0
5	10	10	1,0	0	1	1	0
6	5	2	0,4	0	1	1	1
Total bobot				100	80	85	100
Total keuntungan				40	34	51	55

keterangan :

->  1 = barang dimasukan.
->  0 = barang tidak dimasukan.

->  pada "profit" diutamakan memasukan jumlah barang agar mendekati keuntungan maksimal.

->  pada "weight" diutamakan memasukan jumlah barang agar mendekati beban maksimal.

->  pada "density" diutamakan memasukan jumlah barang agar mendekati harga keuntungan per-unit barang maksimal.

• Pada contoh2, terlihat algoritma greedy dengan ketiga strategi pemilihan objek tidak berhasil memberikan solusi optimal.  Solusi optimal permasalah ini adalah X = (0, 1, 1, 0, 0, 0) dengan total keuntungan = 55.

                     

Sekian untuk artikel kali ini, semoga bermanfaat ^-^

Sumber referensi :

• http://whitenote03.blogspot.co.id/2016/10/knapsack-problem.html
• http://bloglogika.blogspot.co.id/2011/01/knapsack-problem.html
• https://hendryprihandono.wordpress.com/2009/01/03/knapsack-problem-dengan-algoritma-dan-metode-greedy/
• http://nurmaghany.blogspot.co.id/2012/01/knapsack-algoritma.html

Related Posts: