phantom11's blog

When to use greedy???
By phantom11, 13 years ago, In English
Hello everyone!! I just covered the dynamic programming and greedy methods from T.H.Cormen book but I have not understood 1 thing.
How can we come to a conclusion whether a program can be solved by greedy method or not???Plz answer my question
Any help would be appreciated.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think, that you read this book not very detailed. Read about Matroid's and they "links" with prof of gready algo's
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hmmm... Are you sure there isn't answer on your question in the same book you've covered ? :D

Anyway...
You should use greedy method when you are sure that it will lead to best solution.
But it's usually really tricky to prove it, so I believe that at the end it's all about sense and experience... :D
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Try to solve problems with tag "greedy" from Codeforces problemset. May be after a few problems you will feel the difference with the dynamic programming.  
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ya fine.I think I have to solve many problems to get the idea..Thanks.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You may use greedy algo if you still have an ability to get an optimal solution after you did a greedy choice.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
1. If you can use DP, use DP.
2. If there is a greedy solution you are not sure, use DP.
but, 3. If you can prove a greedy solution, use greedy.

Greedy, DP and graph problems are very similar in some view. (e.g. Dijkstra on DP with cycles, etc.)
P. S. IMHO, Matroid's are too abstract and useless here.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    2.1. If there is a greedy solution you are not sure, but you have no ideas about DP - try to use greedy.
    → Reply