Как решить это арифметическое переполнение стека
У меня есть и массив с некоторыми элементами, такими как
5, 3, 7
и начальный int A (например, 5 в первом случае). Я должен сделать сложение и вычитание этого числа из элементов массива, чтобы получить максимальное число меньше или равно M (10 в этом случае). Результаты промежуточных операций не могут превышать M , Я могу использовать элемент массива только один раз.
Например, решение для этого случая будет
A = 5
A - 5 = 0
0 + 3 = 3
3 + 7 = 10
10 равно M, конечный результат.
Какой алгоритм можно использовать для решения этой проблемы? Я делаю эту программу на C ++.
Решение
Я не думаю, что есть «умный» алгоритм, который может решить это за линейное или даже полиномиальное время. Боюсь, что единственный жизнеспособный подход — это попробовать все возможные комбинации и выбрать лучшую. Вы можете, однако, использовать некоторые методы, которые концептуально похожи ветвь и связка чтобы получить результат быстрее.
Я бы сделал это так
Во-первых, я бы сгенерировал все возможные комбинации. Для каждого из ваших чисел N вы можете выбрать суммирование или вычитание, поэтому у вас есть 2 варианта. Это означает, что всего у вас есть 2 ^ N возможных вариантов. В вашем примере с N = 3 это будет: ---, --+, -+-, -++, +--, +-+, ++-, +++, (Это похоже на двоичный счет от 0 = 000 до 7 = 111).
На этом этапе вы должны «выполнить» каждую последовательность. С этими номерами (5, 3, 7), первая последовательность означает -5 -3 -7. Вы должны запускать его по одному шагу за раз, и каждый раз проверять, не превышаете ли вы целевой показатель М, потому что это требуется. Поскольку ваше начальное значение A равно 5, это приведет к: 5-5 = 0, а с 0<10 можно продолжить. Тогда 0-3 = -3, что меньше 10, так что все в порядке. Тогда -3-7 = -10 и так как это последняя операция, нам не нужно проверять, что она меньше 10. Таким образом, последовательность действительна, и мы имеем это для --- результат -10. На данный момент это лучший результат (поскольку он единственный), поэтому давайте сохраним последовательность как лучшую последовательность и конечный результат.
Тогда давайте перейдем к следующей последовательности, --+, Опять же, он действителен и окончательный результат равен 4. Это лучший результат на данный момент, поэтому мы можем сохранить эту последовательность — +, перезаписав предыдущий лучший результат.
Продолжая, в -++ мы найдем лучший результат 10, который нельзя улучшить, поэтому мы могли бы на этом остановиться. Если мы не достигаем M, мы должны оценить все последовательности, и в конце мы получим лучшую. Может быть более одного, что приводит к наилучшему результату, например, если у вас есть дубликаты номеров (3 3 может быть либо +3 -3 или -3 +3, последовательности разные, но результат, очевидно, одинаков), поэтому вы можете захотеть хранить лучшие решения в векторе, вместо того, чтобы хранить только одно.
Это был бы основной алгоритм. Теперь давайте попробуем немного его оптимизировать.
До сих пор мы создали все возможные последовательности (из --- в +++) и оценил их все по одному. Однако в некоторых случаях их оценка — пустая трата времени. Например, предположим, что начальное число снова равно A = 5, а цель — M = 10. Если последовательность была как 6 3 4в определенный момент мы попытаемся оценить +--, но это немедленно потерпит неудачу, потому что первый промежуточный результат будет превышать максимальное значение (5 + 6 = 11). Следуя базовому алгоритму, мы переходим к оценке +-+, но это не имеет смысла: очевидно, по той же причине произойдет сбой на том же шаге (первая цифра, то есть 5 + 6). Неверная последовательность началась с +и все последующие варианты выбора знака не имеют значения: все последовательности, начинающиеся с + обязательно недействительны и могут быть отброшены. Таким образом, это означает, что если мы найдем недопустимую последовательность, мы можем отбросить все остальные, которые начинаются как это.
Для этого мы можем сохранить все последовательности в дереве, которое связывает каждый выбор знака с предыдущим. Затем, как только мы найдем неверное решение, мы можем отбросить все остальные, которые начинаются как этот. Например, дерево может быть сохранено как:
Root
/ \
/ \
/ \
/ \
/ \
- +
/ \ / \
- + - +
/ \ / \ / \ / \
- + - + - + - +
и каждая последовательность соответствует серии узлов, которые должны быть исследованы, чтобы достичь одного из листьев. Когда вы посещаете дерево, для каждого узла вы можете рассчитать и сохранить значение последовательности. Поэтому, когда вы достигнете + на первом уровне, вы увидите, что 5 + 6 = 11, что слишком много, и вы пометите весь узел как недействительный, что позволит избежать изучения всех возможных вариантов. Конечно, с N = 3 числами это не будет иметь большого значения, так как всего всего 2 ^ 3 = 8 последовательностей. Но для N = 20 их будет миллион, и экономия времени может быть значительной.
Другие решения
Вот возможный алгоритм:
A = 5
M = 10
highest number = 0
array of numbers = {5, 3, 7}
function()
call recursive function(empty string, index 0, A)
print highest number
recursive function(string of operations used so far, int current element index, int sum so far)
if the length of the string of operations == number of ints in array
if sum so far > highest number
highest number = sum so far
return
B = sum so far + current element
C = sum so far - current element
if B <= M
recursive function(string of operations plus appended '+', int current element index + 1, B)
if C <= M
recursive function(string of operations plus appended '-', int current element index + 1, C)
Основная идея: использовать рекурсию для отслеживания операций сложения и вычитания. Здесь я просто добавил + а также - к строке, и когда строка стала размером массива, я проверил, была ли сумма выше текущей самой высокой. Вы можете увидеть демонстрацию, сделанную на Java Вот. Не стесняйтесь немного поиграть с числами в демоверсии, чтобы увидеть, как это работает.
detector