Решение для мероприятий 1-3
и пояснение метода обратного хода
10
10
10
10
МЕТОД ОБРАТНОГО ХОДА
Рассмотрим вершину,
обведенную красным кружком и выясним, какой набор мероприятий ей соответствует.
1. Суммарные затраты в вершине– 30.
2. В вершину приходят 2 стрелки – гори-зонтальная и наклонная. Но наклонная идет из вершины с затратами 40 и сама требует затрат 10. Т.е. затраты на это набор больше 30 (50 единиц).
3. Горизонтальная стрелка (с затратами 0) идет из вершины с затратами 30. Этот вариант подходит. Выбираем его.
4. В остальные вершины на пути заходит только по одной стрелке, т.е. путь определяется однозначно.
5. ИТОГ: снижение ущерба 40 с мини-мальными затратами 30 обеспечивает проведение только мероприятия 3.
Алгоритм
Находим вершины, из которых
можно попасть в текущую и которые обеспечивают допустимые значения.