Given any problem
- say we have to pick few objects out of N so that the total weight is below W considering all objects of SAME value,
- A variation for this problem can be to have values assigned to each object
- 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:
- greedy approach
- divide and conquer
- 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.)
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.