Greedy Algorithms

What are Greedy Algorithms?

A greedy algorithm is a simple, intuitive algorithm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. Greedy algorithms are used for optimization problems where the goal is to find the maximum or minimum element according to some criteria.

When to Use Greedy Algorithms

Greedy algorithms are most suitable when:

Common Greedy Algorithms

function activitySelection(start, finish) {
  // Assuming activities are sorted by finish time
  const n = start.length;
  let result = [];
  
  // First activity is always selected
  let i = 0;
  result.push(i);
  
  // Consider rest of the activities
  for (let j = 1; j < n; j++) {
    // If this activity has start time greater than or
    // equal to the finish time of previously selected
    // activity, then select it
    if (start[j] >= finish[result[result.length - 1]]) {
      result.push(j);
    }
  }
  
  return result;
}

// Example usage
const start = [1, 3, 0, 5, 8, 5];
const finish = [2, 4, 6, 7, 9, 9];
// Sort activities by finish time (already sorted in this example)
console.log(activitySelection(start, finish)); // [0, 1, 3, 4]

function fractionalKnapsack(weights, values, capacity) {
  const n = weights.length;
  
  // Create array of objects with value-to-weight ratios
  let items = [];
  for (let i = 0; i < n; i++) {
    items.push({
      weight: weights[i],
      value: values[i],
      ratio: values[i] / weights[i]
    });
  }
  
  // Sort by value-to-weight ratio in descending order
  items.sort((a, b) => b.ratio - a.ratio);
  
  let totalValue = 0;
  let currentWeight = 0;
  
  // Take items with highest value-to-weight ratio first
  for (let i = 0; i < n; i++) {
    if (currentWeight + items[i].weight <= capacity) {
      // Take the whole item
      currentWeight += items[i].weight;
      totalValue += items[i].value;
    } else {
      // Take a fraction of the item
      const remainingCapacity = capacity - currentWeight;
      totalValue += items[i].value * (remainingCapacity / items[i].weight);
      break;
    }
  }
  
  return totalValue;
}

// Example usage
const weights = [10, 20, 30];
const values = [60, 100, 120];
const capacity = 50;
console.log(fractionalKnapsack(weights, values, capacity)); // 240

More Greedy Algorithm Examples

Greedy vs. Dynamic Programming

Both greedy algorithms and dynamic programming are used to solve optimization problems, but they differ in their approach:

function coinChangeGreedy(coins, amount) {
  // Sort coins in descending order
  coins.sort((a, b) => b - a);
  
  let count = 0;
  let remainingAmount = amount;
  
  for (const coin of coins) {
    // Take as many as possible of current coin
    count += Math.floor(remainingAmount / coin);
    remainingAmount %= coin;
  }
  
  return remainingAmount === 0 ? count : -1;
}

function coinChangeDP(coins, amount) {
  // Initialize array with infinity
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Proving Greedy Algorithm Correctness

To prove that a greedy algorithm produces the optimal solution, you typically need to:

Common Pitfalls with Greedy Algorithms

Conclusion

Greedy algorithms provide a powerful approach for solving optimization problems with their simplicity and efficiency. While they don't guarantee optimal solutions for all problems, they work remarkably well for many practical applications and often serve as good approximation algorithms when finding the exact optimal solution is computationally expensive.

Next Steps

To continue your learning journey on algorithm design paradigms, explore these related topics:

Related Tutorials