1
$\begingroup$

I have solved a few optimizations problems using dynamic programming, but some of those problems are also solvable by Greedy algorithms which are computationally more efficient to calculate.

For example, the minimum coin change problem is solvable both by dynamic programming and a greedy approach.

How would someone go about proving a problem that is solvable by dynamic programming can also be solvable by a greedy algorithm?

What is the main intuition behind it? What are some of the main properties that greedy problems share and what are the characteristics I should look for?

$\endgroup$
2
  • $\begingroup$ Take a look to Greedoids. $\endgroup$
    – Phicar
    Commented Feb 2, 2018 at 6:29
  • $\begingroup$ @Phicar I have no idea what that means or how it relates to the question I asked. Would be better if you added some more details. $\endgroup$
    – ng.newbie
    Commented Feb 2, 2018 at 8:02

0

Reset to default

You must log in to answer this question.