ГДЗ по информатике 11 класс Босова, номер §11 № 3

§ № Динамическое программирование на графе

В материалах международного конкурса по информатике «Бобёр» есть такая задача, предложенная разработчиками из Нидерландов. Бобёр Билли любит жёлуди. Он хочет поплыть по течению и собрать все жёлуди на островах, мимо которых будет проплывать. Увы, течение реки настолько сильное, что он может плыть только вниз по течению. Какое максимальное количество желудей он сможет собрать? Решите эту задачу, воспользовавшись методом динамического программирования. На рисунке острова расположены последовательными рядами слева направо: 2; затем 0 и 5; затем 7, 1 и 0; затем 0, 5, 2 и 2; затем 2, 3, 0, 4 и 3 желудя. Каждый остров соединён протоками с ближайшими островами следующего ряда по рисунку.

Решение

Применим метод динамического программирования из § . Для каждого острова запишем наибольшее число желудей, которое можно собрать к моменту прибытия на него. Для первого острова это . Для следующего острова берём максимум результатов у всех островов предыдущего ряда, из которых к нему ведёт протока, и прибавляем число желудей на нём.

Во втором ряду получаем сверху вниз: , . В третьем ряду: к верхнему ведёт протока от верхнего острова, поэтому ; к среднему ведут две протоки, поэтому ; к нижнему ведёт протока от нижнего острова, поэтому .

В четвёртом ряду результаты сверху вниз равны: ; ; ; . В пятом ряду также учитываем только протоки, показанные на рисунке: ; ; ; ; .

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

Ответ

желудей; маршрут через острова с , , , и желудями.

Помогло?

Номер §11 № 3