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

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

Ключевые вопросы параграфа

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

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

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

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

Пример 1

Пример 2

Пример 3

• .

Решение

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

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

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

Остановитесь и подумайте:
Учитывая первые пять предметов, . Найдите все значения , равные .

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

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

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

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

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

1Split(v[1],…,v[n]):
2    if v[1] + … + v[n] не делится целочисленно на 3:
3        return false
4    V = (v[1] + … + v[n]) / 3
5    split = ... // массив размера (n+1) × (V+1) × (V+1)
6    // заполнить массив split значениями false
7    split[0][0][0] = true
8    for i from 1 to n:
9        for s1 from 0 to V:
10            for s2 from 0 to V:
11                split[i][s1][s2] = split[i−1][s1][s2]
12                if s1 >= v[i]:
13                    split[i][s1][s2] = split[i][s1][s2] OR split[i - 1][s1 - v[i]][s2]
14                if s2 >= v[i]:
15                    split[i][s1][s2] = split[i][s1][s2] OR split[i - 1][s1][s2 - v[i]]
16    return split[n][V][V]

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

Что дальше

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

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

А пока вы не ушли дальше — закрепите материал на практике:

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

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

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