8.7. Задача «Сувениры»

Авторы: Алексей Толстиков, Александр Куликов

В этой статье вы научитесь находить оптимальный способ расставить скобки в арифметическом выражении, чтобы получить наибольшее значение. Задача учит динамическому программированию с двумя таблицами — для минимальных и максимальных значений подвыражений. Вы увидите, как даже простое выражение требует аккуратного перебора всех вариантов и рекурсивного деления на подзадачи.

Ключевые вопросы статьи

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

Условие задачиУсловие задачи

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

• Входные данные: Первая строка содержит целое число . Вторая строка содержит целые числа , разделённые пробелами.
• Выходные данные: Вывести 1, если можно разделить на три поднабора с одинаковыми суммами; в противном случае — вывести 0.
• Ограничения: , для всех .

Пример 1

Пример 2

Пример 3

• .

РешениеРешение

Рассмотрим решение задачи. Обозначим как .

1. Разделить набор из  предметов на три части возможно, только если их общая ценность делится на три. То есть , где — это целое число.
2. Так, нам необходимо разделить чисел на три части, где сумма чисел в каждой части равна .
3. Одна из этих частей содержит -й трофей (с ценностью ).
4. Если мы его уберём, то получим разделение первых трофеев на три части таким образом, что ценность двух из них будет равна , а сумма оставшейся части — .

Вместо разделения всех предметов, попробуем решить более мелкую задачу, состоящую в делении первых предметов на части с ценностью , и . Если такое разделение возможно, мы присваиваем (в противном случае — ) и отмечаем, что пираты могут разделить добычу честно, только если .

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

• -й предмет принадлежит первой части. Тогда . Убрав его из первой части, мы разделим первые чисел на три части так, что сумма первых двух частей составит и , то есть .
• -й предмет принадлежит второй части. Как и в предыдущем случае, и .
• -й предмет принадлежит третьей части. Тогда .

Так, значение можно вычислить, посмотрев на

Базовый случай для этого рекуррентного соотношения: и , если .

Split(v[1],…,v[n]):
    if v[1] + … + v[n] не делится целочисленно на 3:
        return false
    V = (v[1] + … + v[n]) / 3
    split = ... // массив размера (n+1) × (V+1) × (V+1)
    // заполнить массив split значениями false
    split[0][0][0] = true
    for i from 1 to n:
        for s1 from 0 to V:
            for s2 from 0 to V:
                split[i][s1][s2] = split[i−1][s1][s2]
                if s1 >= v[i]:
                    split[i][s1][s2] = split[i][s1][s2] OR split[i - 1][s1 - v[i]][s2]
                if s2 >= v[i]:
                    split[i][s1][s2] = split[i][s1][s2] OR split[i - 1][s1][s2 - v[i]]
    return split[n][V][V]

Время выполнения составляет .

Что дальшеЧто дальше

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

Далее — финальная статья раздела. В ней мы кратко обобщим ключевые идеи, которые вы встретили, и покажем, как они складываются в систему.

Ключевые выводы статьи

• Порядок выполнения операций влияет на результат арифметического выражения — важно правильно расставить скобки.
• Можно эффективно найти максимальное значение, если сохранять минимумы и максимумы всех подвыражений в таблицах.
• Динамическое программирование позволяет избежать повторных вычислений и уменьшает время работы с экспоненциального до кубического.
• Даже при небольшом числе операций количество возможных расстановок скобок велико — поэтому важно автоматизировать перебор.