Jurnal : OPTIMASI STRATEGI ALGORITMA GREEDY UNTUK MENYELESAIKAN PERMASALAHAN KNAPSACK 0-1. Oleh : Paryati, Jurusan Teknik Informatika UPN "Veteran" Yogyakarta


Knapsack problem bisa digambarkan, 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 kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.

Dalam menghadapi masalah di atas, Jurnal ini menggunakan metode greedy yang mana 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. 

Penyelesaian dengan Greedy
Masalah : Terdapat data objek dimana w adalah berat objek, p adalah keuntungan/profit dari setiap objek, W adalah kapasitas knapsack.
Dengan perjanjian bahwa objek dimasukkan satu persatu kedalam knapsack. Sekali benda dimasukkan kedalam knapsack maka tidak dapat dikeluarkan lagi.
Data awal :
w1  = 6;    p1  = 12
w2  = 5;    p2  = 15  
w3  = 10;  p3  = 50  
w4  = 5;    p4  = 10
Kapasitas knapsack W = 16

Dari data diatas kita bisa langsung mengetahui nilai pi/wi dengan cara membagi nilai p1 dengan p2 dan seterusnya, sehingga kita dapatkan tabel seperti berikut:


Properti Benda
i
Wi
pi
pi/wi
status
1
6
12
2

2
5
15
3

3
10
50
5

4
5
10
2


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.

Algoritma :
1. Urutkan secara menurun objek-objek berdasarkan profitnya.
2. Masukkan objek yang dapat ditampung knapsack yang mempunyai profit paling besar kedalam knapsack.
3. Cek jika knapsack masih dapat menampung objek lagi maka ulangi langkah 2
4. Knapscak penuh atau tidak dapat memuat objek lagi.

Properti Benda
i
wi
pi
pi/wi
status
3
10
50
5
Diambil
2
5
15
3
Diambil
1
6
12
2
Tidak
4
5
10
2
Tidak

2. Greedy by Weight
Pada setiap langkah Knapsack diisi dengan obyek yang mempunyai berat yang paling ringan. Strategi ini mencoba memaksimumkan keuntungan dengan memasukan sebanyak mungkin objek kedalam knapsack.

Algoritma :
1. Urutkan secara menaik objek-objek berdasarkan weight/beratnya.
2. Masukkan objek yang dapat ditampung knapsack yang mempunyai weight paling ringan kedalam knapsack.
3. Cek jika knapsack masih dapat menampung objek lagi maka ulangi langkah 2.
4. Knapscak penuh atau tidak dapat memuat objek lagi.

Properti Benda
i
wi
pi
pi/wi
status
2
5
15
3
Diambil
4
5
10
2
Diambil
1
6
12
2
Diambil
3
10
50
5
Tidak


3. Greedy by density (pi/wi)
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.

Algoritma :
1. Urutkan secara menurun objek-objek berdasarkan densitasnya(pi/wi).
2. Masukkan objek yang dapat ditampung knapsack yang mempunyai densitas paling besar kedalam knapsack.
3. Cek, Jika knapsack masih dapat menampung objek lagi maka ulangi langkah 2.
4. Knapscak penuh atau tidak dapat memuat objek lagi.

Properti Benda
i
Wi
pi
pi/wi
status
3
10
50
5
Diambil
2
5
15
3
Diambil
4
5
10
2
Tidak
1
6
12
2
Tidak