Greedy
В тази секция ще разгледаме как алчни стратегии понякога могат да бъдат приложени в състезателни задачи. Ще видим няколко популярни задачи, чието решение е базирано на greedy, и няколко по-оригинални, в които то е ключът към решението. За този тип задачи няма много теория, която може да ви помогне - основното е да почнете да познавате кога алчна стратегия може да бъде приложена и кога - не. За съжаление в много задачи само ще изглежда, че тя е възможна, но реално ще има случаи, в които няма да работи правилно. Повечето задачи, в които това е така, се решават с Динамично Оптимиране, което ще разгледаме малко по-късно.Подходяща тема, която можете да разгледате, е тази за Алчни стратегии.
Една от известните задачи, базирани на алчна стратегия, вече разгледахме в секцията за сортиране - това беше задачата MaxNumber. Друга доста "стандартна" е Schedule, която с дадените ограничения може да бъде решена и с bruteforce, но съществува много по-ефективно алчно решение за нея. Донякъде известна задача от интервюта е Codes. Останалите варират по сложност на алчното наблюдение, което трябва да направите - в някои то е много очевидно, докато в други съвсем не е!
Codes
4
|
9
Names
23
|
13
Next
21
|
23
Hidden
25
|
16
Charming
14
|
22
Shoes Again
18
|
15
Casino
15
|
34
Schedule
14
|
9
Strength
30
|
67
Odds
32
|
60
Pairing - Easy
20
|
35
Expression
43
|
75
Boys and Girls
22
|
64
TSP
34
|
47
Andor
6
|
4
Pairing - Hard
7
|
17
Scrabble
15
|
46
Anagrams
21
|
49
Blood
7
|
37
Bytecoin
3
|
27