Algorithm na Neman Zari (Greedy Search) a cikin C++- Bayani, Misali da Lambobi

Algorithm ɗin Bincike na Greedy hanya ce ta warware matsala wacce koyaushe ke zaɓar mafi kyawun zaɓi a kowane mataki ba tare da la'akari da tasirin yanke shawara na dogon lokaci ba. Duk da yake baya bada garantin gano mafi kyawun mafita a duniya, wannan hanyar sau da yawa tana aiki da sauri kuma tana da sauƙin aiwatarwa.

Yadda Ake Aiki

1. Farawa: Fara da komai ko farkon bayani.
2. Zaɓin Mafi Kyau na Gida: A kowane mataki, zaɓi mafi kyawun zaɓi na cikin gida dangane da aikin haƙiƙa ko ƙayyadaddun ma'auni.
3. Aiwatar da Zaɓi: Aiwatar da mafi kyawun zaɓi zuwa mafita na yanzu.
4. Maimaita: Maimaita ta matakai 2 zuwa 4 har sai ba za a iya yin mafi kyawun zaɓi na gida ba.

Misali: Knapsack Problem

Yi la'akari da Knapsack Problem, inda muke da jakar jaka tare da matsakaicin nauyi da jerin abubuwa masu nauyi da ƙima. Manufar ita ce zabar abubuwa don haɓaka jimillar ƙima a cikin jakar jakar. Hanyar Neman Zari don wannan matsala ita ce zabar abubuwa bisa mafi girman darajar-da-nauyi.

Misalin Code a 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;  
}  

A cikin wannan misalin, muna amfani da hanyar Neman Zari don warware Knapsack Problem. Muna rarrabuwar abubuwa dangane da faɗuwar darajar-zuwa-nauyi kuma zaɓi abubuwa tare da mafi girman rabo wanda har yanzu ya dace da iyakar nauyin jakar jakar.