Creator Media

Greedy secara harfiah memiliki arti tamak atau rakus. Selanjutnya, algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Persoalan optimasi hanya ada dua macam yaitu maksimasi dan minimasi. Algoritma greedy membentuk solusi langkah demi langkah. Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

Pada setiap langkahnya merupakan pilihan, untuk membuat langkah optimum lokal dengan harapan bahwa langkah sisanya mengarah ke solusi optimum global. Prinsip dari algoritma greedy menurut Ghozali, Setiawan, dan Furqon (2017) adalah mengambil sebanyak mungkin apa yang dapat diperoleh sekarang. Algoritma greedy merupakan metode yang sering digunakan untuk menyelesaikan integer knapsack problem. Pan dan Zhang (2018), menyelesaikan integer knapsack problem dengan algoritma greedy mempunyai kompleksitas waktu O n n ( log .) Metode algoritma ini tidak selalu menyelesaikan dengan hasil yang optimal, tetapi dapat menghasilkan solusi optimal lokal yang mendekati solusi optimal global dengan waktu yang cepat.

Untuk memilih barang yang akan dimasukkan ke dalam knapsack terdapat beberapa strategi dari metode algoritma greedy dari Juwita, Susanto dan Halomoan (2017) adalah :

Strategi Algoritma Greedy

1. 1. Greedy by Profit

      Setiap langkah di knapsack problem diisi dengan barang yang mempunyai keuntungan terbesar. Strategi ini bertujuan untuk memaksimalkan keuntungan dengan memilih barang yang paling menguntungkan terlebih dahulu. Tahap awalnya adalah mengurutkan secara menurun barang-barang berdasarkan value/ profit barang. Kemudian barang-barang diambil satu persatu sampai kapasitas tempatnya penuh atau sudah tidak ada yang dapat dimasukkan lagi.

   2. Greedy by Weight

      Setiap langkah di knapsack problem diisi dengan barang yang mempunyai berat paling ringan. Strategi ini bertujuan untuk memaksimalkan keuntungan dengan memasukkan barang sebanyak mungkin. Tahap awalnya adalah mengurutkan secara menurun barangbarang berdasarkan berat barang yang paling ringan. Kemudian barang-barang diambil satu persatu sampai kapasitas tempatnya penuh atau sudah tidak ada yang dapat dimasukkan lagi.

   3. Greedy by Density

      Setiap langkah di knapsack problem diisi dengan barang yang mempunyai p i w i dimana p adalah value/ profit, w adalah weight (berat) dan i n = (1,2,3,…, ). Strategi ini bertujuan untuk memaksimalkan keuntungan dengan memilih barang yang mempunyai p i w i (density) terbesar. Tahap awalnya adalah mencari dan mengurutkan secara menurun barang-barang berdasarkan p i w i barang. Kemudian barang-barang diambil satu persatu sampai kapasitas tempatnya penuh atau sudah tidak ada yang dapat dimasukkan lagi (Kellerer, Pferschy dan Pisinger, 2004).

Pembahasan lainnya :

• 1. Konsep Dasar Stack
  2. Jenis-Jenis Binary Tree
  3. Pengertian Knapsack Problem
  4. Contoh Soal 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