For the Knapsack problem

while knapsack is not full
  put the best valued item in the knapsack

What does “best” mean? ? Or ratio ?

Efficiency: (from sorting and iterating over items to add them ).

Greedy algorithms make a sequence of local optimizations, and it might not make it to the global solution.

Pros and cons of greedy algorithms

  • Pro: really easy to implement
  • Pro: really fast ()
  • Con: does not always get to the best solution (not really optimized?)
  • Con: we don’t know how close to optimal it is