Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

When to use greedy???
Автор 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.
→ Ответить