SOLUSI KNAPSACK PROBLEM DENGAN METODE GREEDY..

Di kehidupan sehari-hari, kita sering dipusingkan dengan media penyimpanan yang terbatas padahal diharuskan menyimpan beberapa objek kedalam media tersebut. Bagaimana caranya mengatur objek yang dipilih dan seberapa besar objek tersebut disimpan?

Dari permasalahan tersebut, munculah suatu permasalahan yang dikenal dengan “Permasalahan Knapsack” atau “Knapsack Problem”. Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

Jenis-Jenis Knapsack Problem:

• 0/1 Knapsack problem
  Setiap barang hanya tersedia 1 unit, take it or leave it.

• Fractional Knapsack problem
  Barang boleh dibawa sebagian saja (unit dalam pecahan). Versi problem ini menjadi masuk akal apabila barang yang tersedia dapat dibagi-bagi misalnya gula, tepung, dan sebagainya.

• Bounded Knapsack problem
  Setiap barang tersedia sebanyak N unit (jumlahnya terbatas).

• Unbounded Knapsack problem
  Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas

Nah, dalam menyelesaikan masalah ini saya akan menggunakan Metode Greedy. Apa itu Greedy? Definisi : Metode yang digunakan untuk memecahkan persoalan optimasi dengan pencarian solusi optimum. 

 

   Ada 2 macam persoalan optimasi:

  

   1.  Maksimasi (maximization)
   2.  Minimasi (minimization)

Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin. Prinsip greedy: “take what you can get now!”.

 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 sbesar-besarnya dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong. 

Contoh 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

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

Contoh 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

Pada contoh 2, 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.

Kesimpulan: Algoritma greedy tidak selalu berhasil menemukan solusi optimal untuk masalah 0/1 Knapsack.

Tulisan ini dibuat untuk memenuhi tugas  mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi Teknik Informatika Fakultas Teknik UHAMKA.

Referensi:

1. hendryprihandono.wordpress.com/2009/01/03/knapsack-problem-dengan-algoritma-dan-metode-greedy/
2. kevinkarundeng.wordpress.com/2012/11/05/contoh-soal-algoritma-greedy-dan-knapsack-problem/
3. bloglogika.blogspot.co.id/2011/01/knapsack-problem.html
4. nurmaghany.blogspot.co.id/2012/01/knapsack-algoritma.html