Algoritma Pencarian Serakah (Greedy Search) di C++- Penjelasan, Contoh dan Kode

Algoritma Greedy Search adalah pendekatan pemecahan masalah yang selalu memilih pilihan terbaik yang tersedia pada setiap langkah tanpa mempertimbangkan dampak jangka panjang dari keputusan tersebut. Meskipun tidak menjamin menemukan solusi optimal global, metode ini sering bekerja dengan cepat dan mudah diterapkan.

Bagaimana itu bekerja

1. Inisialisasi: Mulailah dengan solusi kosong atau awal.
2. Pilihan Optimal Lokal: Pada setiap langkah, pilih pilihan optimal lokal berdasarkan fungsi tujuan atau kriteria yang ditentukan.
3. Terapkan Pilihan: Terapkan pilihan optimal ke solusi saat ini.
4. Ulangi: Ulangi langkah 2 hingga 4 hingga tidak ada pilihan lokal yang lebih baik yang dapat dibuat.

Contoh: Knapsack Problem

Pertimbangkan Knapsack Problem, di mana kita memiliki ransel dengan berat maksimum dan daftar barang dengan bobot dan nilai. Tujuannya adalah memilih item untuk memaksimalkan nilai total dalam ransel. Pendekatan Pencarian Serakah untuk masalah ini adalah memilih item berdasarkan rasio nilai-ke-berat tertinggi.

Contoh Kode di C++

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
struct Item {  
    int weight;  
    int value;  
};  
  
bool compare(Item a, Item b) {  
    double ratioA =(double)a.value / a.weight;  
    double ratioB =(double)b.value / b.weight;  
    return ratioA > ratioB;  
}  
  
double greedyKnapsack(int maxWeight, std::vector<Item>& items) {  
    double totalValue = 0.0;  
  
    std::sort(items.begin(), items.end(), compare);  
  
    for(const Item& item: items) {  
        if(maxWeight >= item.weight) {  
            totalValue += item.value;  
            maxWeight -= item.weight;  
        } else {  
            totalValue +=(double)maxWeight / item.weight * item.value;  
            break;  
        }  
    }  
  
    return totalValue;  
}  
  
int main() {  
    int maxWeight = 10;  
    std::vector<Item> items = {{2, 6}, {5, 12}, {3, 8}, {7, 14}, {4, 10}};  
    double maxValue = greedyKnapsack(maxWeight, items);  
  
    std::cout << "Max value in knapsack: " << maxValue << std::endl;  
  
    return 0;  
}  

Dalam contoh ini, kami menggunakan pendekatan Greedy Search untuk menyelesaikan Knapsack Problem. Kami mengurutkan item berdasarkan rasio nilai-terhadap-berat yang menurun dan memilih item dengan rasio tertinggi yang masih sesuai dengan batas berat ransel.