Algartam Cuardaigh Greedy (Greedy Search) i C++- Míniú, Sampla agus Cód

Is cur chuige réitigh fadhbanna é an t-algartam Greedy Search a roghnaíonn i gcónaí an rogha is fearr atá ar fáil ag gach céim gan smaoineamh ar thionchar fadtéarmach an chinnidh. Cé nach ráthaíonn sé go bhfaighidh tú an réiteach is fearr ar fud an domhain, is minic a oibríonn an modh seo go tapa agus is furasta é a chur i bhfeidhm.

Conas a oibríonn sé

1. Túsú: Tosaigh le réiteach folamh nó tosaigh.
2. Rogha Áitiúil is Fearr: Ag gach céim, roghnaigh an rogha is fearr go háitiúil bunaithe ar an bhfeidhm oibiachtúil nó ar na critéir shainithe.
3. Rogha a Chur i bhFeidhm: Cuir an rogha is fearr i bhfeidhm ar an réiteach reatha.
4. Déan: Déan arís trí chéimeanna 2 go 4 go dtí nach féidir rogha áitiúil níos fearr a dhéanamh.

Sampla: Knapsack Problem

Smaoinigh ar an Knapsack Problem, áit a bhfuil mála droma againn le huasmheáchan agus liosta de na míreanna a bhfuil meáchain agus luachanna acu. Is é an sprioc ná míreanna a roghnú chun an luach iomlán sa mhála droma a uasmhéadú. Is é cur chuige Cuardach Greedy don fhadhb seo ná míreanna a roghnú bunaithe ar an gcóimheas luach-go-meáchain is airde.

Sampla Cód i 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;  
}  

Sa sampla seo, úsáidimid an cur chuige Cuardach Greedy chun an Knapsack Problem. Déanaimid na míreanna a shórtáil bunaithe ar an gcóimheas íslitheach luach-go-meáchain agus roghnaímid míreanna leis an gcóimheas is airde atá fós laistigh de theorainn meáchain an mhála droma.