DEV Community

Susritha09
Susritha09

Posted on

Dynamic Programming Vs Greedy

Dynamic Programming:

It just solves problems by combining the sub problems to solutions only of the sub problems were independent.
It can be used for solving both mathematical optimization method and computer programming method.
For example, it can be used for finding the shortest path in graph.
• Many decision sequence may be generated.
• Highly reliable
• Bottom-up approach
• There is no special set of feasible solution
• Less Efficiency
• Overlapping subproblems choose feasible solution

Alt Text


The algorithm used is:

Alt Text

Greedy Method:

Greedy method solves problems step by step which leads to global optimization solution.
• Generates a single decision sequence
• Less reliable
• Top to bottom approach
• Contain a special set of feasible set of solutions.
• More efficiency
• Overlapping subproblems cannot be handled.

Alt Text
Algorithm for greedy is:
Greedy(D,n)
//In Greedy approach D is domain
//from which solution is to be obtained of size n
//Initially assume
solution<-0
for i<-1 to n do{
s<-select(D)
if(Feasible solution,s))then
Solution<-Union(Solution,s)
}
return solution

Top comments (0)