Greedy algorithms

A greedy algorithm follows the problem-solving heuristic of making the locally optimal choice (the best solution at the time) at each stage with the hope of finding a global optimum (global best solution). It does not evaluate the bigger picture like a dynamic programming algorithm does.

Let's take a look at how we can solve the min-coin change and knapsack problems we covered in the dynamic programming topic using the greedy approach.

Note

We covered some other greedy algorithms in this book in  Chapter 9 , Graphs, such as Dijkstra's algorithm, Prim's algorithm, and Kruskal's algorithm.

The min-coin change problem

The min-coin change problem can also be resolved with a greedy algorithm. Most of the time, the result is also optimal, but for some denominations, the result will not be optimal.

Let's take a look at the algorithm:

function MinCoinChange(coins){ 
  var coins = coins; //{1} 
 
  this.makeChange = function(amount) { 
   ...