Greedy /ˈɡriːdi/

I often encounter optimization problems where there are multiple possible ways to reach a solution. The challenge is determining which approach is actually best. Even when a solution works, it’s difficult to know whether it is truly optimal. If I choose option A, could option B produce a better result? Is there any option C that achieves the same goal with fewer steps?

Learning about Greedy algorithms helped me think about these problems more systematically. Instead of exploring every possible solution, I learned to focus on making the best choice available at each step and then verify whether that strategy leads to an optimal result. This way of thinking has made me feel much more comfortable when approaching optimization problems.

Greedy Algorithm is an approach that chooses the best available option at each step, hoping that these local optimal choices will lead to a globally optimal solution.

Idea:

At each step, choose the option that looks best at the moment without reconsidering future decisions.

For example, consider the coin change problem. You have 1,000, 2,000, 5,000, 10,000, 20,000, 50,000, 100,000, 200,000, 500,000. We need to make 280,000 VND using the available denominations:

280,000 -> get 200,000

80,000 -> get 50,000

30,000 -> get 20,000

10,000 -> get 10,000

=> result could be: 200,000 + 50,000 + 20,000 + 10,000 => the minimum number of banknotes is 4.

There are two important conditions that make Greedy applicable:

1. Greedy choice property: a locally optimial choice can be part of a globally optimal solution.

2. Optimal Substructure: the optimal solution to a problem can be constructed from optimal solutions to its subproblems.

Greedy fails for denominations {1, 3, 4}. Suppose we need to make 6 => (4-1-1) => not the optimal solution (3-3)

Here are some classic programming problems:

• Activity selection: select the maximum number of non-overlapping activities. Always choose the activity with the earliest finish time.
• Fractional Knapsack: items can be taken fractionally. Choose items with the highest value-to-weight ratio first.
• Minimum spanning tree: used in Dijkstra’s algorithm.
• Shortest path: used in Dijkstra’s algorithm.

Some indicator to determine Greedy Algorithm

1. Can the problem be solved by sorting and selecting? - sort by time, end time, weight, profit, deadline,…

2. Can a decision be made without revisiting it later? If no => Greedy not suitable. If yes => Greedy might be suitable.

3. Does it require optimization? max/min/largest/smallest - these problems are often candidates for Greedy Algorithms, Dynamic Programming or Graph Algorithms.

Thinking in problem

1. Does it need sorting?
2. Does it have any criteria to choose the best solution at the moment?
3. Does it require optimization?
4. Does it have counterexample?
5. Some time you need to sort and loop to finish them to optimize the result => it might need Greedy.

Peseudo code

Whole Idea

Prepare the data 

while (hasSelection) {
  choosing the best available option
  commit
}

Some pattern of Greedy

1. Always take the largest (or smallest) valid choice

for (coin of coinsDes){
  takeMaxPossible(coin)
}

2. Sort and Select

Always choose the activity

activities.sort((a,b)=> a.end - b.end))
for(activity of activities) {
  if(activity.start >= lastEnd){
    select(activity);
  }
}

3. Priority Queue/Heap

Using for Meeting Rooms, Task scheduler, CU scheduling. Continiously select the best candidate available at the current moment.

while(heap.notEmpty()){
  const best = heap.pop();
  process(best)
}

4. Greedy on Graph

Using for Dijkstra. Repeatedly select the unvisited node with the smallest known distance.

while(pq.notEmpty()){
  const node = pq.popMinDistance();
  relaxNeighbors(node);
}

Practice with Vietnamese exchange

function withdraw(amount: number){
  const denominations = [
    500000,
    200000,
    100000,
    50000,
    20000,
    10000,
    5000,
    2000,
    1000,
  ];
  const result = {};
  for(const denomination of denominations){
    if (amount >= denomination) {
      result[denomination] = Math.floor(amount / denomination);
      amount %= denomination;
    }
  }
  return result;
}

console.log(withdraw(786000));

// Expect 
// [
//  { denomination: 500000, count: 1 },
//  { denomination: 200000, count: 1 },
//  { denomination: 50000, count: 1 },
//  { denomination: 20000, count: 1 },
//  { denomination: 10000, count: 1 },
//  { denomination: 5000, count: 1 },
//  { denomination: 1000, count: 1 }
// ]

Conclusion

Greedy algorithm was one of the first optimization techniques I learned, but it also took me some time to understand when it actually works. Greedy is not as a specific algorithm, but as a way of thinking: making the best decision available now and proving that it leads to the optimal result in the end.