Menyelesaikan Knapsack Problem dengan menggunakan Algoritma Greedy

Knapsack Problem

• Knapsack dapat diartikan sebagai karung atau kantung.
• Karung digunakan untuk memuat sesuatu.
• Dan tentunya tidak semua objek dapat ditampung di dalam karung. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung.
• Setiap objek itupun tidak harus kita masukkan seluruhnya. Tetapi bisa juga sebagian saja.
• knapsack 0/1, yaitu suatu objek diambil seluruh bagiannya atau tidak sama sekali.
• Setiap objek mempunyai   nilai   keuntungan   atau   yang   disebut   dengan
• Tujuan ingin mendapatkan profit yang Untuk   mendapatkan profit maksimal Belum   tentu   menggunakan banyak   objek   yang   masuk akan menguntungkan. Bisa saja hal yang sebaliknya yang terjadi.
  • Cara terbaik agar menguntungkan : bukan hanya dari hasilnya optimal tetapi juga banyaknya langkah yang dibutuhkan

 

Knapsack 0/1

Diberikan n buah objek dan sebuah knapsack dengan  kapasitas  bobot  W.

Setiap  objek  memiliki properti bobot (weigth) wi dan keuntungan(profit) pi.

persoalan  adalah  memilih  objek-objek    yang    dimasukkan    ke    dalam    knapsack sedemikian sehingga  memaksimumkan keuntungan. Total   bobot   objek   yang   dimasukkan   ke dalam   knapsack   tidak   boleh   melebihi   kapasitas knapsack.

 

Solusi  persoalan  dinyatakan  sebagai  vektor n-tupel:

X = {x1, x2, …  , xn}

xi = 1 jika objek ke-i dimasukkan ke dalam knapsack,

xi = 0 jika objek ke-i tidak dimasukkan.

 

Persoalan  0/1  Knapsack  dapat  kita  pandang  :

sebagai   mencari   himpunan   bagian   (subset)   dari  keseluruhan objek yang muat ke dalam knapsack dan memberikan total keuntungan terbesar.

 

Penyelesaian dengan Greedy:

1. Greedy by Profit

Pada setiap langkah Knapsack diisi dengan obyek yang mempunyai keuntungan terbesar.

Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan  terlebih dahulu.

Pertama kali dilakukan adalah menurutkan secara menurun obyek-obyek berdasarkan profitnya .  Kemudian obyek-obyek yang dapat ditampung oleh knapsack diambil satu persatu sampai knapsack penuh atau (sudah tidak ada obyek lagi yang bisa dimasukan).

Data awal :

w1  = 6;    p1  = 12

w2  = 5;    p2  = 15

w3  = 10;  p3  = 50

w4  = 5;    p4  = 10

Kapasitas knapsack W = 16

 

2. Greedy by Weight

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai berat paling ringan.  Strategi ini mencoba memaksimumkan keuntungan dengan memasukan sebanyak mungkin objek kedalam knapsack.

Pertama kali yang dilakukan adalah mengurutkan secara menaik objek-objek berdasarkan weight-nya. Kemudian obyek-obyek yang dapat ditampung oleh knapsack diambil satu persatu sampai knapsack penuh atau (sudah tidak ada obyek lagi yang bisa dimasukan).

 

3. Greedy By Density

Pada setiap langkah, knapsack diisi dengan obyek yang mempunyai densitas terbesar (perbandingan nilai dan berat terbesar).

Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

Pertama kali yang dilakukan adalah mencari nilai profit per unit/ density dari tiap-tiap objek. Kemudian obyek-obyek diurutkan berdasarkan densitasnya.

Kemudian obyek-obyek yang dapat ditampung oleh knapsack diambil satu persatu sampai knapsack penuh atau (sudah tidak ada obyek lagi yang bisa dimasukan).

 

CONTOH:

Kapasitas M=20, dengan jumlah barang =3

Berat Wi masing-masing barang (W1,W2,W3) sebesar (18,15,10)

Nilai Profit masing-masing barang (P1,P2,P3) sebesar  (25,24,15)

 

Pilih Barang dengan nilai profit maksimal

P1=25 –>  x1=1.  batas atas nilai

P2=24  –> x2=2/15.

P3=15 –>  x3 =0. batas bawah nilai.

 

Pilih barang dengan berat minimal

W1 = 18  –>  x1=0.  batas bawah

W2=15  –>  x2 = 2/3

W3=10 –>  x3=1. batas atas.

 

Pilih barang dengan menghitung perbandingan yang terbesar dari profit dibagi Berat (Pi/Wi) diurut secara tidak naik.

 

P1/w1=25/18   (1.38)  –> x1=0. karena terkecil x1=0

P2/w2=24/ 15   (1.6) –> x2=1.    karena terbesar x2=1

P3/w3=15/10  (1.5) –> x3=1/2    dicari dengan fungsi pembatas x3=1/2.

 

Tabel

Solusi	(x1,x2,x3)	Σwixi	Σpixi
Pi max	1,2/15,0	20	28.2
Wi min	0,2/3,1	20	31.0
Pi/Wi max	0,1,1/2	20	31.5

 

Nilai profit maksimal  = 31.5.