Блог пользователя phantom11

Автор phantom11, 13 лет назад, По-английски
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.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I think, that you read this book not very detailed. Read about Matroids.

Забыл переключить язык.Спс, Егор.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think, that you read this book not very detailed. Read about Matroid's and they "links" with prof of gready algo's
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.  
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You may use greedy algo if you still have an ability to get an optimal solution after you did a greedy choice.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.