Write the difference between greedy method and dynamic programming
person
brightness_auto
1 Answer
| Greedy method | Dynamic programming |
|---|---|
| Does not guarantee an optimal solution | Guarantees an optimal solution |
| Assumes sub-problems do not overlap | Assumes sub-problems overlap |
| Does little work | Does more work |
| Only considers current choices | Considers future choices |
| Constructs the solution from a set of feasible choices | There is no specialized set of feasible choices |
| Selects a locally optimum choice | Selects globally optimum choices |
| No concept of memorization | Employs memorization |
| Examples: Knapsack, Job scheduling with deadlines, Kruskal, Prim’s | Examples: All pair shortest path, 0/1 Knapsack, Travelling salesman problem, LCS |