1
$\begingroup$

Given any problem

  1. say we have to pick few objects out of N so that the total weight is below W considering all objects of SAME value,
  2. A variation for this problem can be to have values assigned to each object
  3. Another variation: multiple copies of the same object allowed.

There can be other such problems including string similarity, longest sub-sequence, interval scheduling etc.

How to decide for the approach to use to solve a given abstract problem ? Let me put it this way: What are the cases when we prefer each one of these over the others:

  1. greedy approach
  2. divide and conquer
  3. dynamic programming

(Correct me if i am wrong, dynamic programming is considered as a special case of Divide and conquer. still here for discussion i am putting it separately.)

EDIT:

Some times we can use 2 approaches to solve the same problem. Its difficult to decide which one to follow.

eg. If we are given price of share p(i) on day "i". We can sell the share on day "j" > "i". Given the values of prices of shares in advance, we can compute the value p(j) - p(i) such that maximum profit is incurred. This can be solved using dynamic programming and even by divide and conquer.

$\endgroup$

1 Answer 1

1
$\begingroup$

Well, in general, I will consider a divide and conquer algorithm when the problem has a natural recursive nature (such as sorting, or tree-related algorithms). If I'm trying to solve an optimization problem (for example, the fractional knapsack problem), then I will consider a greedy or dynamic programming algorithm. I should also note that greedy solutions are really just a subset of dynamic programming solutions. Part of it also comes from intuition and practice. After knowing how several types of algorithms are solved, you can normally get a pretty good intuition as to how to solve a similar type of problem.

I also believe that the book, Introduction to Algorithms (CLRS), provides a nice discussion on this.

EDIT: The link Do dynamic programming and greedy algorithms solve the same type of problems? provides a good answer to your question as well :)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .