Question

Для прокладки электрического кабеля длиной 167 метров необходимо подготовить канал из резиновых труб. Есть трубы по 5 метров и 7 метров. Сколько труб (общее количество) необходимо взять, чтобы количество соединений было минимальным?

Answer 1

25 труб
21 по 7 метров
4 по 5

Answer 2

Для решения этой задачи можно воспользоваться алгоритмом динамического программирования.

Создадим массив DP длиной 168 (длина кабеля + 1), где DP[i] будет содержать минимальное количество соединений для прокладки кабеля длиной i метров.

Изначально заполним массив бесконечными значениями, кроме DP[0], которое будет равно 0, так как для прокладки кабеля длиной 0 метров нам не понадобятся трубы.

Затем переберем все возможные длины кабеля от 1 до 167 и для каждой длины будем находить минимальное количество соединений, используя уже посчитанные значения.

Для каждой длины i метров будем рассматривать два варианта: либо использовать трубу длиной 5 метров, либо использовать трубу длиной 7 метров. В случае использования трубы длиной 5 метров, количество соединений будет равно DP[i-5] + 1. В случае использования трубы длиной 7 метров, количество соединений будет равно DP[i-7] + 1. Мы выбираем вариант с минимальным количеством соединений.

После перебора всех длин кабеля, DP[167] будет содержать минимальное количество соединений для прокладки кабеля длиной 167 метров.