Question

Which of the following algorithms can be solved by Greedy method as well as Dynamic programming?​

Answer 1

Answer:

This is the Answer....

Explanation:

Approximately" is hard to define, so I'm only going to address the "accurately" or "optimally" aspect of your questions.)

There's a nice discussion of the difference between greedy algorithms and dynamic programming in Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (Chapter 16, pages 381-383 in the second edition).

With respect to your first question, here's a summary of what they have to say. Both dynamic programming and greedy algorithms can be used on problems that exhibit "optimal substructure" (which CLRS defines by saying that an optimal solution to the problem contains within it optimal solutions to subproblems). However, in order for the greedy solution to be optimal, the problem must also exhibit what they call the "greedy-choice property"; i.e., a globally optimal solution can be arrived at by making locally optimal (greedy) choices. In contrast, dynamic programming is good for problems that exhibit not only optimal substructure but also overlapping subproblems. (This means that a particular subproblem can be reached in multiple ways. The dynamic programming algorithm calculates the value of each subproblem once and then can reuse these every time the algorithm revisits them.)