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