0

1.1kviews

Differentiate between greedy approach and dynamic programming.

written 6.9 years ago by satishmanje93 • 250

modified 2.8 years ago by sagarkolekar ★ 11k

analysis of algorithms

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

0

24views

written 2.8 years ago by Krishna_Agrawal • 2.7k

•   modified 2.8 years ago

S.No.	Greedy Approach	Dynamic Programming
1.	In Greedy, there is no such guarantee of getting optimal solution.	In dynamic, it will generate an optimal solution using Principle of optimality.
2.	More efficient as compared to a dynamic approach.	Less efficient as compared to a greedy approach.
3.	Generates a single decision sequence.	Many decision sequence may be generated.
4.	It follows top-down approach.	It follows bottom-down approach.
5.	It requires almost no memory.	It requires a lot of memory for memorisation / tabulation.
6.	In Greedy, overlapping problems can not be handled.	In Dynamic, overlapping problems can be handled easily.
7.	It makes decision considering the first stage.	It makes decision at every stage.
8.	Examples are Fractional knapsack, Shortest path.	Examples are 0/1 Knapsack.

ADD COMMENT SHARE EDIT