Решение задачи 3 про бобра Билли: Максимум желудей

Для решения задачи о бобре Билли воспользуемся методом динамического программирования. Нам нужно найти путь от самого левого острова до самого правого, на котором сумма собранных желудей будет максимальной. Решение: 1. Проанализируем количество желудей на каждом острове (узле графа) по столбцам слева направо: - 1-й столбец: 2 желудя. - 2-й столбец: 0 (верхний), 5 (нижний). - 3-й столбец: 8 (верхний), 1 (средний), 0 (нижний). - 4-й столбец: 0 (верхний), 4 (второй сверху), 2 (третий сверху), 2 (нижний). - 5-й столбец: 2 (верхний), 2 (второй сверху), 0 (третий сверху), 4 (нижний). - 6-й столбец: 3 (нижний). - 7-й столбец: 0 (конечный остров). 2. Будем вычислять максимальное количество желудей \( S \), которое можно собрать, попав в каждый конкретный остров. Формула для каждого острова: \[ S_{текущий} = желуди_{на\_острове} + \max(S_{предыдущих\_связанных\_островов}) \] 3. Расчет по шагам: - Старт: 2. - 2-й столбец: Верхний: \( 0 + 2 = 2 \) Нижний: \( 5 + 2 = 7 \) - 3-й столбец: Верхний: \( 8 + 2 = 10 \) Средний: \( 1 + \max(2, 7) = 1 + 7 = 8 \) Нижний: \( 0 + 7 = 7 \) - 4-й столбец: Верхний: \( 0 + 10 = 10 \) Второй: \( 4 + \max(10, 8) = 4 + 10 = 14 \) Третий: \( 2 + \max(8, 7) = 2 + 8 = 10 \) Нижний: \( 2 + 7 = 9 \) - 5-й столбец: Верхний: \( 2 + 10 = 12 \) Второй: \( 2 + \max(10, 14) = 2 + 14 = 16 \) Третий: \( 0 + \max(14, 10) = 14 \) Нижний: \( 4 + \max(10, 9) = 4 + 10 = 14 \) - 6-й столбец: Верхний (пустой): \( 0 + \max(12, 16) = 16 \) Нижний (3 желудя): \( 3 + \max(14, 14) = 17 \) - 7-й столбец (финиш): \[ S_{max} = 0 + \max(16, 17) = 17 \] Ответ: Максимальное количество желудей, которое сможет собрать бобер Билли, равно 17.