*****************
Greedy Algorithms
*****************
A greedy algorithm is a simple, intuitive algorithmic paradigm that follows the
problem-solving heuristic of making the locally optimal choice at each stage
with the hopes of finding the global optimum.

Characteristics
===============
+ Heuristic
+ Local optimum
+ Intuitive
+ No long term planning
+ Approximate, no guarantee to find the best solution
+ Less time complexity than exact algorithms

Relationships with other paradigms
==================================
Greedy algorithms and backtracking are both decision-making paradigms in
algorithm design, distinguished by their approach to finding solutions.

.. list-table::
  :header-rows: 1

  * - Greedy
    - Backtracking
  * - Approximate
    - Exact
  * - Make a decision
    - Make a decision
  * - Never look back
    - Look back
  * - No long term planning
    - Long term planning
  * - Less time complexity
    - More time complexity
  * - May fail to find the best solution
    - Always find the best solution by finding all solutions

Application Domain
==================
**Solve Optimization (find best) problems.** Many combinatorial optimization
problems can be solved by a greedy algorithm.

+ Graph problems

  * Shortest path: Dijkstra's algorithm
  * Minimum spanning tree: Prim's algorithm, Kruskal's algorithm
  * Graph coloring

+ Bin packing problem
+ Activity selection problem
+ Fractional knapsack problem
+ Huffman coding

Example Problems
================

.. toctree::

  /gen-programming/problems/greedy-bin-packing
  /gen-programming/problems/greedy-huffman