Dynamic Programming Vs Greedy Algorithm
Dynamic Programming Vs Greedy Algorithm
In this article we will talk about Dynamic Programming Vs Greedy Algorithm. Both the methods are used to solve the optimization problems. Finding of best solution from the set of solutions is called an optimization problem.
Greedy approach is simple method. It finds the solution by taking the next best move without exploring its future consequences. So sometimes it ends up with sub optimal solution. Greedy algorithm does not provide optimal solution for all problem instances. However, due to its simplicity and less computational time, greedy algorithms are preferred over any other method if it provides optimal solution.
On the other hand, dynamic programming always ensure the optimal solution. Dynamic programming requires more memory as it stores the solution of each and every possible sub problems in the table. It does lot of work compared to greedy approach, but optimal solution is ensured.
In following table, we have compared dynamic programming and greedy approach on various parameters.
| Dynamic Programming | Greedy Approach |
| It guarantees an optimal solution. | It does not guarantee an optimal solution. |
| Sub problems in dynamic programming are overlapping. | Sub problems in greedy algorithm do not overlap. |
| It does more work due to splitting of problem at every possible point. | It does little work due to splitting problem at specific points only. |
| It considers the future choices while selects the current choice. | Only considers the current choice without looking about future. |
| There is no specialized set of feasible choices. | Construct the solution from the set of feasible solutions. |
| Select choice which is globally optimum. | Select choice which is locally optimum. |
| Employ memorization. | There is no concept of memorization. |
| Examples: Make a change problem Knapsack problem Assembly line scheduling Multistage graph Matrix chain multiplication |
Examples: Binary Knapsack problem Fractional knapsack problem Job scheduling problem Activity selection problem Huffman Coding Optimal storage on tapes Optimal merge pattern |
Additional Reading: Read More