2.4 Greedy

• idea of Greedy
  1. Solve a problem by making a sequence of decisions
  2. Decisions are made one by one in some order
  3. Each decision is made using a greedy criterion At each stage we make a decision that appears to be the best at the time
  4. A decision, once made, is (usually) not changed later
• You need a greedy criterion to make a local decision
• Examples: makin change, 0/1 knappack, activity selection (largest subset) sorted according to their finishing time, topological orders. Dijkstra, Kruskal, prim and sollin
• Applications: Container Loading, 0/1 knapsack problem, Topological sorting, Bipartite cover, Single-source shortest paths, Minimum-cost spanning trees.