METODE GREEDY (Knapsack problem)

Metode Greedy digunakan untuk memecahkan persoalan optimasi. Persoalan optimasi adalah persoalan mencari solusi optimum Persoalan optimasi ada 2 Maksimasi

Minimasi

Contoh Masalah Optimasi:Penukaran UangDiberikan uang senilai A. Tukar A dengan koin-koin uang yang ada.Berapakah jumlah minimum koin yang diperlukan untuk penukaran uang tersebut.

Persoalan Minimasi.

Contoh 1: tersedia banyak koin 1, 5, 10, 25

32 = 1 + 1 + … + 1 (32 koin)32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)32 = 10 + 10 + 10 + 1 + 1 (5 koin)Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)

Greedy = rakus, tamak Algoritma greedy membentuk solusi langkah per langkah (step by step). Pada setiap langkah terdapat banyak pilihan yang perlu dieksplorasi. Sehingga, pada setiap langkah harus dibuat keputusan yang terbaik dalam

menentukan pilihan.(keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya).

Pada setiap langkah membuat pilihan optimum lokalDengan harapan bahwa langkah sisanya mengarah kesolusi optimum global.

Metode Greedy digunakan dalam menyelesaikan masalah Optimal Storage on Tapes Problem Knapsack Problem Minimum Spanning Tree Problem Shortest Path Problem

Penjelasan Storage on Tape Problen ada pada SLIDE.

Knapsack Problem

Knapsack dapat diartikan sebagai karung, kantung, atau buntilan. 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 profit. Tujuan ingin mendapatkan profit yang maksimal. Untuk mendapatkan profit maksimal Belum tentu menggunakan banyak objek yang masuk akan menguntungkan. Bisa saja hal yang sebaliknya yang terjadi. o 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 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 WightPada 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 DensityPada 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).

Perbandingan hasil:

Penggunaan 3 strategi diatas tidak menjamin akan memberikan solusi optimal.

CONTOH 2:

Kapasitas M=20, dengan jumlah barang =3Berat Wi masing-masing barang (W1,W2,W3) (18,15,,10)Nilai Profit masing-masing barang (P1,P2,P3) (25,24,15)

Pilih Barang dengan nilai profit maksimal P1=25 x1=1. batas atas nilaiP2=24 x2=2/15.P3=15 x3 =0. batas bawah nilai.

Pilih barang dengan berat minimalW1 = 18 x1=0. batas bawahW2=15 x2 = 2/3W3=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=0P2/w2=24/ 15 (1.6) x2=1. karena terbesar x2=1P3/w3=15/10 (1.5) x3=1/2 dicari dengan fungsi pembatas x3=1/2.

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

Nilai profit maksimal = 31.5.

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.

Contoh kasus knapsack

w1 = 10;  p1 = 2 w2 = 5;     p2 = 3 w3 = 15;   p3 = 5 w4 = 7;     p4 = 7 w5 = 6;     p5 = 1 w6 = 18;   p6 = 4 w7 = 3;     p7 = 1

M = 15

Jawaban :    

 

 

Properti objek Greedy by Solusi

Optimali 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.

Knapsack Problem adalah permasalahan seseorang yang dibatasi kapasitas knapsack yang tetap dan harus diisi dengan item yang sangat bernilai.

Implementasinya: Pengisian barang di gudang, optimalisasi karyawan dalam suatu perusahaan, dll.

Jenis knapsack problem yang dibahas: 0-1 Knapsack Problem. Item-item knapsack ini bersifat indivisible (tidak dapat dibagi) dan dapat diselesaikan menggunakan algoritma dynamic programming

0 – 1 Knapsack: (0) item tidak diambil, (1) item diambil. W: kapasitas knapsack Setiap item i memiliki bobot w dan bernilai c (w dan c adalah integer) Algoritma 0-1 Knapsack

for w = 0 to W

c[0,w] = 0

for i = 1 to n

c[i,0] = 0

for w = 1 to W

if wi ≤ w

if vi + c[i-1,w-wi] > c[i-1,w]

c[i,w] = vi+ c[i-1,w- wi]

else

c[i,w] = c[i-1,w]

else c[i,w] = c[i-1,w]

Contoh

i 1 2 3

wi 2 4 1

vi 3 4 3

n  = 3

W = 3

Hasilnya:

Untuk mengetahui isi dari knapsack yang menghasilkan optimal profit, dilakukan cara berikut :

c(3,3) = 6 > c(2,3)  , maka   i3 =  1

c(3,3) = 6 = 3+ c(2,2)

c(2,2) = 3  =  c(1,2) , maka  i2 =  0

c(1,2) = 3 > c(0,2)  , maka   i1 =  1

c(1,2) = 3 = 3+ c(0,0)

Dengan demikian, knapsack berisi (1,0,1)

Dengan weight = 2 +1 = 3

Value =  3 + 3 = 6

 

Knapsack Problem merupakan suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang mempunyai weight dan profit

 masing‐masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum. Knapsack problem merupakan salah satu dari persoalan klasik yang banyak ditemukan dalam

 literatur‐literatur lama dan hingga kini permasalahn tersebut masih sering ditemukan dalam kehidupan sehari‐hari. Contoh nyata dari Knapsack Problem ini misalnya,  jika

 ada seorang pedagang barang kebutuhan rumah tangga yang berkeliling menggunakan gerobak. Tentu saja gerobaknya memiliki kapasitas maksimum, sehingga ia tidak bisa memasukkan semua

 barang dagangannya dengan seenak hatinya. Pedagang tersebut harus memilih barang‐barang mana saja yang harus ia angkut, dengan pertimbangan berat dari barang yang

 dibawanya tidak melebihi kapasitas maksimum gerobak dan memaksimalkan profit dari barang‐barang yang ia bawa