Algoritmos voraces

Algoritmos voraces

Los algoritmos voraces toman decisiones localmente óptimas esperando un óptimo global. Son más rápidos que DP pero no siempre dan la solución óptima.

Problema de selección de actividades

function activitySelection(activities) {
  // Sort by finish time
  activities.sort((a, b) => a.end - b.end);
  
  const selected = [activities[0]];
  let lastEnd = activities[0].end;
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }
  return selected;
}

Cambio de monedas (voraz - no siempre óptimo)

function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a); // Descending
  const result = [];
  
  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return amount === 0 ? result : null;
}

// Works for standard coin systems (1, 5, 10, 25)
// May not work for arbitrary coin systems!

Mochila fraccionaria

function fractionalKnapsack(items, capacity) {
  // Sort by value/weight ratio

  

    
Aprende más
    

      
        
GeeksforGeeks: Greedy
        
Aprende sobre algoritmos voraces y sus aplicaciones.
      
      
        
LeetCode: Greedy
        
Resuelve problemas optimizados con enfoques voraces.
      
    
  

  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  
  let totalValue = 0;
  
  for (const item of items) {
    if (capacity >= item.weight) {
      totalValue += item.value;
      capacity -= item.weight;
    } else {
      totalValue += item.value * (capacity / item.weight);
      break;
    }
  }
  return totalValue;
}