В каком порядке объединять файлы? — разбор задачи

Условие

Есть четыре файла размером $2$ $3$ $4$ и $8$ условных единиц. Одна операция объединяет любые два файла в новый файл, размер которого равен сумме их размеров. Стоимость операции равна этому же размеру; старые два файла исчезают. Нужно получить один общий файл за три операции. Найдите наименьшую суммарную стоимость и докажите, что меньше нельзя.

О задаче · Подростки и взрослые

Тема: Оптимизация
Для кого: Подростки и взрослые
Уровень библиотеки: Следующий шаг · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Последнее объединение всегда стоит $17$ но два предыдущих могут иметь разную стоимость.

Подсказка 2

После выбора первой пары останутся три файла. Какую пару среди них выгоднее объединить?

Разобрать решение по шагам

Отделите неизбежную плату

Общий размер никогда не меняется и равен $17$ Поэтому последняя операция при любом плане стоит $17$ Порядок влияет лишь на стоимость первых двух объединений: файл, возникший рано, может оплачивать копирование повторно.

Постройте план стоимостью $31$

Сначала объединяем $2$ и $3$ платим $5$ Теперь размеры $4$ $5$ $8$ Объединяем $4$ и $5$ платим $9$ Наконец объединяем $8$ и $9$ платим $17$ Всего $5+9+17=31$

Исключите более дешёвый план

Первой можно выбрать одну из шести пар. После этого остаются три файла; так как последняя плата фиксирована, выгоднее объединить два наименьших из них. Все варианты первых действий:

Первая пара	Лучшая полная стоимость
$2$ и $3$	$31$
$2$ и $4$	$32$
$2$ и $8$	$34$
$3$ и $4$	$33$
$3$ и $8$	$34$
$4$ и $8$	$34$

Это исчерпывает все первые действия и лучшие продолжения после них. Минимум действительно $31$

Маленькие файлы объединяются раньше

012 + 3 = 5первая стоимость — 5

024 + 5 = 9вторая стоимость — 9

038 + 9 = 17суммарно 5+9+17

Ответ

Минимальная суммарная стоимость — $31$ объединить $2$ и $3$ затем $5$ и $4$ затем $9$ и $8$

Главная идея

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

Как заметить эту идею в другой задаче

Стоимость объединения равна сумме размеров, а промежуточные суммы используются снова. Маленькие элементы выгодно объединять раньше, чтобы они участвовали в повторных оплатах.

Возможная ошибка

Объединить всё «сразу» и назвать стоимость $17$ По условию операция принимает только два файла, поэтому промежуточные копирования тоже оплачиваются.

Источник и примечания

Источник и редакция

Авторская учебная задача на классическую идею. Формулировка и разбор — Popov Academy.

Проверь себя

Размер каждого исходного файла увеличили ровно вдвое. Во сколько раз изменится минимальная общая стоимость?

Ответ к дополнительной задаче

Тоже вдвое: она станет $62$ Для любого порядка все промежуточные размеры и стоимости удваиваются. Соответствие между планами сохраняется, поэтому удваивается и минимум.

Продолжить тему: Поиск и алгоритмы →

Тема, знания и приёмы

Поиск и алгоритмы · Нужна школьная база

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

Приёмы решения: Оценка и достижимость · Ограниченный перебор

Задать вопрос по задаче →

Условие

Отделите неизбежную плату

Постройте план стоимостью 313131

Исключите более дешёвый план

Источник и редакция

Условие

Дополнительная задача

Постройте план стоимостью $31$