Algoritma Dan Pemrograman: Algoritma Greedy

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.

- Persoalan optimasi (optimization problems):
   persoalan mencari solusi optimum.

Hanya ada dua macam persoalan optimasi:
1.  Maksimasi (maximization)
2. Minimasi (minimization)

Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah;
 
Pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa
   memperhatikan konsekuensi ke depan
   (prinsip “take what you can get now!”)

2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir
   dengan optimum global.


Tinjau masalah penukaran uang:

Strategi greedy:
Pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa.

Misal: A = 32, koin yang tersedia: 1, 5, 10, dan 25
Langkah 1: pilih 1 buah koin 25  (Total = 25)
Langkah 2: pilih 1 buah koin 5    (Total = 25 + 5 = 30)
Langkah 3: pilih 2 buah koin 1    (Total = 25+5+1+1= 32)

Solusi: Jumlah koin minimum = 4     (solusi optimal!)

Solusi permasalahan Integer Knapsack

Greedy by profit.
- Pada setiap langkah, pilih objek yang mempunyai keuntungan terbesar.
- Mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu.

Greedy by weight.
- Pada setiap langkah, pilih objek yang mempunyai berat teringan.
- Mencoba memaksimumkan keuntungan dengan dengan memasukkan sebanyak mungkin objek ke dalam knapsack.

Greedy by density.
- Pada setiap langkah, knapsack diisi dengan objek yang mempunyai pi /wi  terbesar.
- Mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

Greedy by profit & density memberi solusi optimal

Ketiga solusi gagal memberi solusi

Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. 

Solusi permasalahan Fractional Knapsack

1. Hitung harga pi/wi , i = 1, 2, ..., n
2. Urutkan seluruh objek berdasarkan nilai pi/wi dari besar ke kecil
3. Panggil FractinonalKnapsack 

• Strategi pemilihan objek berdasarkan densitas pi /wi terbesar akan selalu memberikan solusi optimal. 
• Agar proses pemilihan objek berikutnya optimal, maka kita urutkan objek berdasarkan pi /wi yang menurun,  sehingga objek berikutnya yang dipilih adalah objek sesuai dalam urutan itu.
• Jika p1/w1 >= p2/w2 >= ... >= pn/wn maka algoritma greedy dengan strategi pemilihan objek berdasarkan pi /wi terbesar menghasilkan solusi yang optimum.