criskgl
8/7/2019 - 2:26 PM

Greedy

Greedy Algorithms

Algorithm paradigm that follows the `problem solving approach of making locally optimal choice at each stage with the hope of finding a a global optimum.

  • Greedy algorithms work the same way as dynamic programming but memoization cannot be applied.

PROS

  • Simple
  • Easy implementation
  • Acceptable runtime

CONS

  • very often doesnt provide globally optimum solution.

So... When to use?

Problems in which greedy approach work have the next properties:

  • 1.Choice property: A global optimum can be arrived at by selecting a local optimum.
  • 2.Optimal substructure: An optimal solution to the problem contains an optimal solution to subproblems.
greedy.java
content_copyfile_download
//GENERAL APPROACH TO GREEDY
Algorithm Greedy(arr, n){
  for(i=1 to n){
    x = select(arr)
    if feasible(x){
      solution = solution + x;
    }
  }
}