В этом параграфе вы научитесь находить оптимальный способ расставить скобки в арифметическом выражении, чтобы получить наибольшее значение. Задача учит динамическому программированию с двумя таблицами — для минимальных и максимальных значений подвыражений. Вы увидите, как даже простое выражение требует аккуратного перебора всех вариантов и рекурсивного деления на подзадачи.
Ключевые вопросы параграфа
- Почему результат арифметического выражения зависит от порядка скобок?
- Как использовать динамическое программирование для перебора всех вариантов группировки?
- Как устроены таблицы для хранения минимальных и максимальных значений подвыражений?
Условие задачи
Три пирата делят свою добычу, в которую входят предметов разной ценности. Получится у вас помочь разделить добычу поровну?
- Входные данные: Первая строка содержит целое число . Вторая строка содержит целые числа , разделённые пробелами.
- Выходные данные: Вывести 1, если можно разделить на три поднабора с одинаковыми суммами; в противном случае — вывести 0.
- Ограничения: , для всех .
Пример 1
Ввод |
Вывод |
4 |
0 |
Пример 2
Ввод |
Вывод |
1 |
0 |
Пример 3
Ввод |
Вывод |
13 |
1 |
- .
Решение
Рассмотрим решение задачи. Обозначим как .
- Разделить набор из предметов на три части возможно, только если их общая ценность делится на три. То есть , где — это целое число.
- Так, нам необходимо разделить чисел на три части, где сумма чисел в каждой части равна .
- Одна из этих частей содержит -й трофей (с ценностью ).
- Если мы его уберём, то получим разделение первых трофеев на три части таким образом, что ценность двух из них будет равна , а сумма оставшейся части — .
Вместо разделения всех предметов, попробуем решить более мелкую задачу, состоящую в делении первых предметов на части с ценностью , и . Если такое разделение возможно, мы присваиваем (в противном случае — ) и отмечаем, что пираты могут разделить добычу честно, только если .
Остановитесь и подумайте:
Учитывая первые пять предметов, . Найдите все значения , равные .Представьте, что вы уже составили двоичный двумерный массив для всевозможных значений и . Сможете ли вы использовать этот массив, чтобы составить массив ?
Предположим, что . Тогда первые чисел можно разделить на три части таким образом, чтобы сумма чисел в первой части составляла , а сумма чисел во второй части — .
- -й предмет принадлежит первой части. Тогда . Убрав его из первой части, мы разделим первые чисел на три части так, что сумма первых двух частей составит и , то есть .
- -й предмет принадлежит второй части. Как и в предыдущем случае, и .
- -й предмет принадлежит третьей части. Тогда .
Так, значение можно вычислить, посмотрев на
Базовый случай для этого рекуррентного соотношения: и , если .
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]
Время выполнения составляет .
Что дальше
Теперь вы умеете вычислять максимальное значение арифметического выражения, расставляя скобки в нужном порядке. Вы научились использовать динамическое программирование с запоминанием минимальных и максимальных значений и применять аккуратные рекурсивные формулы.
Далее — финальный параграф главы. В нём мы кратко обобщим ключевые идеи, которые вы встретили, и покажем, как они складываются в систему.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Порядок выполнения операций влияет на результат арифметического выражения — важно правильно расставить скобки.
- Можно эффективно найти максимальное значение, если сохранять минимумы и максимумы всех подвыражений в таблицах.
- Динамическое программирование позволяет избежать повторных вычислений и уменьшает время работы с экспоненциального до кубического.
- Даже при небольшом числе операций количество возможных расстановок скобок велико — поэтому важно автоматизировать перебор.