Greedy Search Algorithm in C++ - Explanation, Example and Code

The Greedy Search algorithm is a problem-solving approach that always chooses the best available option at each step without considering the long-term impact of the decision. While it doesn't guarantee finding the globally optimal solution, this method often works quickly and is straightforward to implement.

How It Works

1. Initialization: Start with an empty or initial solution.
2. Local Optimal Choice: At each step, choose the locally optimal choice based on the objective function or defined criteria.
3. Apply Choice: Apply the optimal choice to the current solution.
4. Repeat: Iterate through steps 2 to 4 until no better local choice can be made.

Example: Knapsack Problem

Consider the Knapsack Problem, where we have a knapsack with a maximum weight and a list of items with weights and values. The goal is to select items to maximize the total value in the knapsack. A Greedy Search approach for this problem is to select items based on the highest value-to-weight ratio.

Code Example in 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;
}

In this example, we use the Greedy Search approach to solve the Knapsack Problem. We sort the items based on the descending value-to-weight ratio and select items with the highest ratio that still fit within the knapsack's weight limit.