## Greedy Algorithms: Make Change --- ## I'm LizThe.Dev/ Founding team of: - Hackbright Academy (Prof) - HipCamp (CTO) - Galvanize Web Development Program (Prof) - Enki.com (CTO) --- ## Greedy Algorithms Greedy algorithms make the **locally optimal choice** at each step. --- # Analogy: Eating a Pie If allowed to eat a single slice, which is best? ```mermaid pie title Pie Slices "A" : 40 "B" : 30 "C" : 20 "D" : 10 ``` --- ## 🦹‍ Jewel Thief's Dilemma You've broken into a museum, and you only have the time to steal 3 jewels, which 3 do you take? ```mermaid graph TD; A[Available Jewels: $5m, $4.5m, $2.53m, $11m, $4m] ``` --- ## Greedy Approach: Making Change ```mermaid sequenceDiagram participant Q as Quarters participant D as Dimes participant N as Nickels participant P as Pennies Note over Q: Change needed: 67¢ Q->>D: 2 Quarters (50¢) || Change left: 17¢ D->>N: 1 Dime (10¢) || Change left: 7¢ N->>P: 1 Nickel (5¢) || Change left: 2¢ P->>P: 2 Pennies (2¢) || Change left: 0¢ ``` --- ## Greedy Approach: Nearest Neighbor This is known as the nearest neighbor heuristic. ```mermaid graph LR; A[Start City] --> B[Nearest City]; B --> C[Next Nearest City]; C --> D[Another Nearest City]; D --> E[Return to Start]; ``` --- ## Shortest Route ```mermaid graph TB; A[City A] -->|5 miles| B[City B]; A -->|3 miles| C[City C]; B -->|6 miles| D[City D]; C -->|5 miles| D; A -->|7 miles| D; ``` --- # When to Use a Greedy Approach --- ## Optimal Substructure The problem can be broken down into smaller, simpler subproblems, and the optimal solution to the problem contains the optimal solutions to the subproblems. **Use Greedy**: ✅ When the problem has optimal substructure. --- ## Greedy Choice Property A global optimum can be reached by selecting a local optimum. **Avoid Greedy**: ❌ When selecting a local optimum does not necessarily lead to a global optimum. --- ## No Need for Backtracking Once a decision is made, it never has to be reconsidered. **Use Greedy**: ✅ When decisions are final and don't need to be reconsidered. --- ## Simple and Intuitive Solution **Avoid Greedy**: ❌ When the problem is complex, and the greedy approach oversimplifies it. --- ## Known to be Efficient The greedy approach is known to provide an efficient solution for the specific problem. **Avoid Greedy**: ❌ When there are more efficient or accurate algorithms available. --- ## Understand The Problem Given an array of coin values, and a target change amount, produce an array of coins that represent the coins you would need to make that amount of change. --- ## Understand The Problem Try to be a robot 🤖 Think step-by-step You have coins, worth a certain amount: 25, 10, 5, 1 You have a target value to reach: 16 52 27 101 --- ## Time to Write Down a Plan