Greedy Algorithm
Solve optimization problems by making the best choice at each step.
What is the Greedy Algorithm?
A greedy algorithm is an approach for solving problems by choosing the best possible option at each step, hoping that this leads to the global optimum. Unlike other approaches like dynamic programming or backtracking, greedy algorithms do not reconsider choices once made, making them faster but not always accurate for every problem.
Key Concepts in Greedy Algorithms
- Greedy Choice Property: A locally optimal choice leads to a globally optimal solution.
- Optimal Substructure: The solution to the problem can be constructed from the solutions of its subproblems.
These two properties must be satisfied for a greedy algorithm to provide the correct solution.
Time & Space Complexities
- Time Complexity: Depends on the problem. For example:
- Sorting-based problems (e.g., activity selection):
O(n log n) - Iterative greedy steps:
O(n)
- Sorting-based problems (e.g., activity selection):
- Space Complexity: Typically
O(1)for most greedy problems since decisions are made in-place.
When to Use Greedy Algorithms
Greedy algorithms work well for problems like:
- Optimization Problems: Finding the maximum or minimum value.
- Interval Scheduling: Activity selection, task scheduling.
- Graph Problems: Minimum Spanning Tree (Kruskal's or Prim's), Dijkstra's algorithm for shortest path.
- Resource Allocation: Fractional Knapsack, Huffman coding.
Code Examples
Below is an example of the Fractional Knapsack Problem solved using a greedy approach.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int weight;
int value;
bool operator<(const Item& other) const {
return (double)value / weight > (double)other.value / other.weight;
}
};
double fractionalKnapsack(int capacity, vector<Item>& items) {
sort(items.begin(), items.end());
double totalValue = 0.0;
for (const auto& item : items) {
if (capacity >= item.weight) {
totalValue += item.value;
capacity -= item.weight;
} else {
totalValue += (double)item.value * capacity / item.weight;
break;
}
}
return totalValue;
}
int main() {
vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
int capacity = 50;
double maxValue = fractionalKnapsack(capacity, items);
cout << "Maximum value in Knapsack = " << maxValue << endl;
return 0;
}