Greedy Algorithms

1function greedyCoinChange(coins, amount) {
2  coins.sort((a, b) => b - a); // Largest first
3  let count = 0;
4  let result = [];
5  
6  for (const coin of coins) {
7    while (amount >= coin) {
8      amount -= coin;
9      result.push(coin);
10    }
11  }
12 
13  if (amount === 0) {
14    return result; // Optimal
15  }
16  return null; // Failed to make change
17}

1function fractionalKnapsack(capacity, items) {
2  // 1. Calculate value/weight ratio and sort
3  items.forEach(item => item.ratio = item.value / item.weight);
4  items.sort((a, b) => b.ratio - a.ratio);
5 
6  let totalValue = 0;
7  let currentWeight = 0;
8 
9  for (const item of items) {
10    if (currentWeight + item.weight <= capacity) {
11      // 2. Take the whole item
12      currentWeight += item.weight;
13      totalValue += item.value;
14    } else {
15      // 3. Take a fraction of the item
16      const remainingWeight = capacity - currentWeight;
17      totalValue += item.ratio * remainingWeight;
18      currentWeight += remainingWeight;
19      break; // Knapsack is full
20    }
21  }
22  return totalValue;
23}

1function activitySelection(activities) {
2  // 1. Sort activities by finish time
3  activities.sort((a, b) => a.end - b.end);
4 
5  const result = [];
6  if (activities.length === 0) return result;
7 
8  // 2. Select the first activity
9  result.push(activities[0]);
10  let lastFinishTime = activities[0].end;
11 
12  for (let i = 1; i < activities.length; i++) {
13    const currentActivity = activities[i];
14    
15    // 3. If current activity starts after the last one finished...
16    if (currentActivity.start >= lastFinishTime) {
17      // ...select it and update the last finish time.
18      result.push(currentActivity);
19      lastFinishTime = currentActivity.end;
20    }
21  }
22  return result;
23}