Creator Media

Secara harafiah, greedy berati rakus atau tamak. Algoritma Greedy merupakan algoritma sederhana dan lempang yang paling populer untuk pemecahan persoalan optimasi (maksimum atau minimum). Prinsip greedy adalah “take what you can get now!”, yang digunakan dalam konteks positif. Ada tiga pendekatan dalam menyelesaikan persoalan integer knapsack dengan algoritma Greedy, yaitu :

Contoh Soal Knapsack Problem

1. 1. Greedy by profit

      Pada setiap langkah, knapsack diisi dengan objek yang mempunyai keuntungan terbesar. Strategi ini memcoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu. Pertama kali yang dilakukan adalah mengurutkan secara menurun objekobjek berdasarkan profit-nya. Kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.

   2. Greedy by weight

      Pada setiap langkah, knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini memcoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack. Pertama kali yang dilakukan adalah mengurutkan secara menaik objekobjek berdasarkan weight-nya. Kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau tidak ada objek lagi yang bisa dimasukkan.

      
      
      

   3. Greedy by density

      Pada setiap langkah, knapsack diisi dengan objek yang mempunyai densitas (pi/wi) terbesar. Strategi ini mencoba memaksimumkan keuntungan per unit berat terbesar. Pertama kali yang dilakukan adalah mencari nilai profit per unit (density) dari tiap-tiap objek. Kemudian objek-objek tersebut diurutkan secara menurun berdasarkan density-nya. Kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau tidak ada objek lagi yang bisa dimasukkan.

Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. Bahkan ada kemungkinan ketiga strategi tersebut tidak memberikan solusi optimum.

Pembahasan lainnya :

• 1. Konsep Dasar Stack
  2. Jenis-Jenis Binary Tree
  3. Strategi Algoritma Greedy
  4. Pengertian Knapsack Problem
  5. Algoritma Dynamic Programming
  6. Elemen Elemen Algoritma Greedy
  7. Karakteristik Algoritma Brute Force
  8. Keunggulan Bahasa Pemrograman Java
  9. Pengertian Logaritma dan Sifat-Sifatnya
  10. Efisiensi Algoritma Ditinjau dari 2 Dua Hal
  11. Algoritma Boyer Moore untuk String Matching
  12. Penyelesaian Knapsack Problem dengan Kriteria Greedy