Greedy

В тази секция ще разгледаме как алчни стратегии понякога могат да бъдат приложени в състезателни задачи. Ще видим няколко популярни задачи, чието решение е базирано на greedy, и няколко по-оригинални, в които то е ключът към решението. За този тип задачи няма много теория, която може да ви помогне - основното е да почнете да познавате кога алчна стратегия може да бъде приложена и кога - не. За съжаление в много задачи само ще изглежда, че тя е възможна, но реално ще има случаи, в които няма да работи правилно. Повечето задачи, в които това е така, се решават с Динамично Оптимиране, което ще разгледаме малко по-късно.

Подходяща тема, която можете да разгледате, е тази за Алчни стратегии.

Една от известните задачи, базирани на алчна стратегия, вече разгледахме в секцията за сортиране - това беше задачата MaxNumber. Друга доста "стандартна" е Schedule, която с дадените ограничения може да бъде решена и с bruteforce, но съществува много по-ефективно алчно решение за нея. Донякъде известна задача от интервюта е Codes. Останалите варират по сложност на алчното наблюдение, което трябва да направите - в някои то е много очевидно, докато в други съвсем не е!