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

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

}

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.