Differentiate between greedy approach and dynamic programming.

0

972views

Differentiate between greedy approach and dynamic programming.

written 6.3 years ago by

satishmanje93 • 250

modified 2.2 years ago by

sagarkolekar ★ 11k

analysis of algorithms

ADD COMMENT EDIT

1 Answer

0

22views

written 2.2 years ago by

Krishna_Agrawal • 2.6k

• modified 2.2 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 EDIT

Please log in to add an answer.