Can someone tell me where we use Dynamic/Greedy algorithm and how we trace from the question that it will solved by any one of the above?
Thanks
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Your question is missing some details. Also, it is somewhat broad. I recommend solving several exercises to get a feel for where dynamic programming is useful, and where greedy algorithms are effective. $\endgroup$– Yuval FilmusDec 18, 2016 at 11:09
-
$\begingroup$ My Question is really simple and clear and I have got the answer thanks though . $\endgroup$– Deepak Kumar KhatriDec 23, 2016 at 19:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Greedy Algorithm:
An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems. [1].
Problems that can be solved by a Greedy Algorithm will have two properties:
- Greedy Choice Property;
- Optimal Substructure.
Essentially, Greedy Algorithms solve combinatorial problems having the properties of matroid.
For more detail you can consult Introduction to Algorithm.
Dynamic Programming:
Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them. [2]
Dynamic Programming algorithms are often used for optimization because it will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem.
Now, problems that can be solved by a Dynamic Programming Algorithm will have this necessary condition:
Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. [3]
-
1