Page 195 - Bkhargava_-_Grokaem_algoritmy
P. 195
194 Глава 8. Жадные алгоритмы
Еще раз напомню основные моменты:
D множества похожи на списки, но множества не содержат дубликатов;
о с множествами можно выполнять различные интересные операции -
вычислять их объединение, пересечение и разность.
Вернемся к коду
Продолжим рассматривать исходный пример.
Пересечени е множеств:
covered = states_needed & states_for_station
Множество covered содержит штаты, присутствующие как в states_needed,
так и в states_for _station. Таким образом, covered - множество штатов, не
входящих в покрытие, которые покрываются текущей станuией! Затем мы
проверяем, покрывает ли эта станция больше штатов, чем текущая станция
best_station:
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
www.trk.kg
