Page 228 - Bkhargava_-_Grokaem_algoritmy

Самая длинная общая подстрока 227

при заданных ограничениях. В задаче о рюкзаке требуется максимизи­
ровать стоимость отобранных предметов с ограничениями по емкости
рюкзака.
Q Динамическое программирование работает только в ситуациях, в кото­
рых задача может быть разбита на автономные подзадачи, не зависящие
друг от друга.

Построить решение на базе динамического программирования бывает не­
просто. В этом разделе мы сосредоточимся на этой теме. Несколько общих
рекомендаций:

Q в каждом решении из области динамического программирования стро­
ится таблица;

Q значения ячеек таблицы обычно соответствуют оптимизируемой ха­
рактеристике. Для задачи о рюкзаке значения представляли общую
стоимость товаров;
Q каждая ячейка представляет подзадачу, поэтому вы должны подумать
о том, как разбить задачу на подзадачи. Это поможет вам определиться
с осями.

Рассмотрим еще один пример. Допустим, вы от­
крыли сайт dictionary.com. Пользователь вводит
слово, а сайт возвращает определение. Но если
пользователь ввел несуществующее слово, нуж­
но предположить, какое слово имелось в виду.
Алекс ищет определение «fish~. но он случайно
ввел 4'hish~. Такого слова в словаре нет, но зато
у вас есть список похожих слов.

С.ЛОВА, ПОХО#.МЕ НА "Н!.SН":

• Fl.SH

• Vl.SH

(Это несерьезный пример, поэтому список ограничен всего двумя словами.
Вероятно, на практике такой список будет состоять из тысяч слов.)

www.trk.kg