Algoritma Panelusuran Greedy (Greedy Search) ing C ++- Panjelasan, Tuladha lan Kode

Algoritma Greedy Search minangka pendekatan pemecahan masalah sing tansah milih pilihan sing paling apik sing kasedhiya ing saben langkah tanpa nimbang dampak jangka panjang saka keputusan kasebut. Sanajan ora njamin nemokake solusi sing paling optimal sacara global, cara iki asring dianggo kanthi cepet lan gampang ditindakake.

Cara Kerjane

1. Initialization: Mulai karo solusi kosong utawa dhisikan.
2. Pilihan Optimal Lokal: Ing saben langkah, pilih pilihan optimal lokal adhedhasar fungsi objektif utawa kriteria sing ditemtokake.
3. Aplikasi Pilihan: Aplikasi pilihan optimal kanggo solusi saiki.
4. Baleni: Ulangi langkah 2 nganti 4 nganti ora ana pilihan lokal sing luwih apik.

Tuladha: Knapsack Problem

Coba Knapsack Problem, ngendi kita duwe knapsack karo bobot maksimum lan dhaptar item karo bobot lan nilai. Tujuane kanggo milih item kanggo nggedhekake nilai total ing knapsack. Pendekatan Panelusuran Greedy kanggo masalah iki yaiku milih item adhedhasar rasio nilai-kanggo-bobot sing paling dhuwur.

Tuladha Kode ing 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;  
}  

Ing conto iki, kita nggunakake pendekatan Greedy Search kanggo ngatasi Knapsack Problem. Kita ngurutake item adhedhasar rasio nilai-kanggo-bobot mudhun lan pilih item kanthi rasio paling dhuwur sing isih pas ing watesan bobot knapsack.