(Greedy Search) C++ ਵਿੱਚ ਲਾਲਚੀ ਖੋਜ ਐਲਗੋਰਿਦਮ- ਵਿਆਖਿਆ, ਉਦਾਹਰਨ ਅਤੇ ਕੋਡ

ਲਾਲਚੀ ਖੋਜ ਐਲਗੋਰਿਦਮ ਇੱਕ ਸਮੱਸਿਆ-ਹੱਲ ਕਰਨ ਵਾਲੀ ਪਹੁੰਚ ਹੈ ਜੋ ਫੈਸਲੇ ਦੇ ਲੰਬੇ ਸਮੇਂ ਦੇ ਪ੍ਰਭਾਵ ਨੂੰ ਵਿਚਾਰੇ ਬਿਨਾਂ ਹਰ ਕਦਮ 'ਤੇ ਹਮੇਸ਼ਾ ਸਭ ਤੋਂ ਵਧੀਆ ਉਪਲਬਧ ਵਿਕਲਪ ਚੁਣਦੀ ਹੈ। ਹਾਲਾਂਕਿ ਇਹ ਵਿਸ਼ਵ ਪੱਧਰ 'ਤੇ ਅਨੁਕੂਲ ਹੱਲ ਲੱਭਣ ਦੀ ਗਰੰਟੀ ਨਹੀਂ ਦਿੰਦਾ ਹੈ, ਇਹ ਵਿਧੀ ਅਕਸਰ ਤੇਜ਼ੀ ਨਾਲ ਕੰਮ ਕਰਦੀ ਹੈ ਅਤੇ ਲਾਗੂ ਕਰਨ ਲਈ ਸਿੱਧੀ ਹੁੰਦੀ ਹੈ।

ਕਿਦਾ ਚਲਦਾ

1. ਸ਼ੁਰੂਆਤੀ: ਇੱਕ ਖਾਲੀ ਜਾਂ ਸ਼ੁਰੂਆਤੀ ਹੱਲ ਨਾਲ ਸ਼ੁਰੂ ਕਰੋ।
2. ਸਥਾਨਕ ਅਨੁਕੂਲ ਚੋਣ: ਹਰ ਪੜਾਅ 'ਤੇ, ਉਦੇਸ਼ ਫੰਕਸ਼ਨ ਜਾਂ ਪਰਿਭਾਸ਼ਿਤ ਮਾਪਦੰਡ ਦੇ ਅਧਾਰ 'ਤੇ ਸਥਾਨਕ ਤੌਰ 'ਤੇ ਅਨੁਕੂਲ ਚੋਣ ਚੁਣੋ।
3. ਵਿਕਲਪ ਲਾਗੂ ਕਰੋ: ਮੌਜੂਦਾ ਹੱਲ ਲਈ ਸਰਵੋਤਮ ਵਿਕਲਪ ਨੂੰ ਲਾਗੂ ਕਰੋ।
4. ਦੁਹਰਾਓ: ਕਦਮ 2 ਤੋਂ 4 ਤੱਕ ਦੁਹਰਾਓ ਜਦੋਂ ਤੱਕ ਕੋਈ ਬਿਹਤਰ ਸਥਾਨਕ ਚੋਣ ਨਹੀਂ ਕੀਤੀ ਜਾ ਸਕਦੀ।

ਉਦਾਹਰਨ: Knapsack Problem

'ਤੇ ਵਿਚਾਰ ਕਰੋ Knapsack Problem, ਜਿੱਥੇ ਸਾਡੇ ਕੋਲ ਵੱਧ ਤੋਂ ਵੱਧ ਵਜ਼ਨ ਵਾਲਾ ਨੈਪਸੈਕ ਹੈ ਅਤੇ ਵਜ਼ਨ ਅਤੇ ਮੁੱਲਾਂ ਵਾਲੀਆਂ ਚੀਜ਼ਾਂ ਦੀ ਸੂਚੀ ਹੈ। ਟੀਚਾ ਨੈਪਸੈਕ ਵਿੱਚ ਕੁੱਲ ਮੁੱਲ ਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ ਕਰਨ ਲਈ ਆਈਟਮਾਂ ਦੀ ਚੋਣ ਕਰਨਾ ਹੈ। ਇਸ ਸਮੱਸਿਆ ਲਈ ਇੱਕ ਲਾਲਚੀ ਖੋਜ ਪਹੁੰਚ ਸਭ ਤੋਂ ਉੱਚੇ ਮੁੱਲ-ਤੋਂ-ਵਜ਼ਨ ਅਨੁਪਾਤ ਦੇ ਅਧਾਰ ਤੇ ਆਈਟਮਾਂ ਦੀ ਚੋਣ ਕਰਨਾ ਹੈ।

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;  
}  

ਇਸ ਉਦਾਹਰਨ ਵਿੱਚ, ਅਸੀਂ ਹੱਲ ਕਰਨ ਲਈ ਲਾਲਚੀ ਖੋਜ ਪਹੁੰਚ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ Knapsack Problem । ਅਸੀਂ ਘਟਦੇ ਮੁੱਲ-ਤੋਂ-ਵਜ਼ਨ ਅਨੁਪਾਤ ਦੇ ਆਧਾਰ 'ਤੇ ਆਈਟਮਾਂ ਨੂੰ ਛਾਂਟਦੇ ਹਾਂ ਅਤੇ ਸਭ ਤੋਂ ਉੱਚੇ ਅਨੁਪਾਤ ਵਾਲੀਆਂ ਆਈਟਮਾਂ ਦੀ ਚੋਣ ਕਰਦੇ ਹਾਂ ਜੋ ਅਜੇ ਵੀ ਨੈਪਸੈਕ ਦੀ ਵਜ਼ਨ ਸੀਮਾ ਦੇ ਅੰਦਰ ਫਿੱਟ ਹੁੰਦੀਆਂ ਹਨ।