Knapsack Problem Metode Greddy (Soal Bonus)

Knapsack Problem

Knapsack adalah tas atau karung. Karung digunakan untuk memuat sesuatu. Dan tentunya tidak semua objek dapat ditampung di dalam karung tersebut. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung. 

Penggunaan Metode Greddy salah satunya adalah untuk menyelesaikan permasalahan Knapsack, Knapsack problem bisa di gambarkan, misalnya kita mempunyai kantong 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 dengan kapasitas kantong yang kita miliki supaya bisa mendapatkan keuntungan yang maksimal.

Algoritma Greedy
Teknik  pemrograman  dengan  menggunakan  Greedy  sering  digunakan  untuk permasalahan  optimasi.  Secara  umum  teknik  ini  menggunakan  heuristic  untuk mencari solusi suboptimum sehingga diharapkan solusi optimum.
Pada Greedy  Algorithm ada  beberapa  strategi yang  digunakan untuk  memilih objek yang akan dimasukkan ke dalam knapsack.
  

Jenis-Jenis Knapsack Problem
Terdapat beberapa variasi 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

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

1. Greedy by Profit
   Strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang dengan nilai keuntungan terbesar terlebih dahulu ke dalam Knapsack. 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 
   Strategi ini, kita berusaha memasukan barang semaksimalnya kedalam kantong  barang yang dimasukan terlebih dahulu adalah bobot paling ringan terlebih dahulu, dengan banyaknya barang yang terangkut kita bisa mendapatkan keuntungan semaksimal mungkin.
3. Greedy by density
   Strategi ini mengharapkan keuntungan semaksimal mungkin dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong. 

Tata cara penggunaan Metode Greddy dalam persoalan Knapsack adalah

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

Namun karena Metode Greddy hanya mempertimbangkan keuntungan local dengan harapan mendapat keuntungan global, maka metode ini juga tidak menjamin akan memberikan solusi optimal.

 Contoh masalah Knapsack :

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.

Contoh Soal Knapsack dan Fractional Knapsack :

1.    w₁ = 10;  p₁ = 2

w₂ = 5;     p₂ = 3

w₃ = 15;   p₃ = 5

w₄ = 7;     p₄ = 7

w₅ = 6;     p₅ = 1

w₆ = 18;   p₆ = 4

w₇ = 3;     p₇ = 1

M = 15

Jawaban : 

• 1/0 Knapsack M= 15 

Properti objek				Greedy 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. 

•       Fractional Knapscak M=15

Properti objek				Greedy 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

 Referensi : 

• http://nurmaghany.blogspot.co.id/2012/01/knapsack-algoritma.html
• http://itsmepowel.blogspot.co.id/2012/01/tugas-uas-knapsack.html
• http://sitiekachotimah.blogspot.co.id/2012/04/contoh-soal-knapsack-dan-fractional.html