Поместите операторы "sum" и "multiply" между элементами заданного списка целых чисел, чтобы выражение получило заданное значение

Ответ 1

Пусть A и B - целые положительные числа. Тогда A + B ≤ A & times; B + 1.

Этот маленький факт может быть использован для построения очень эффективного алгоритма.

Определим граф. Узлы графа соответствуют спискам операций, например, [+, & times;, +, +, & times;]. Есть граф из графика node X в граф node Y, если Y можно получить, изменив один + на a & times; в X. Граф имеет источник в node, соответствующий [+, +,..., +].

Теперь выполните поиск по ширине из источника node, построив график по ходу. Например, при расширении node [+, & times;, +, +, & times;] вы можете (возможно построить) подключиться к узлам [& times;, & times;, +, +, & times;], [+, & times;, & times;, +, & times;] и [+, & times;, +, & times;, & times;]. Не расширяйте до node, если результат его вычисления больше r + k (O), где k (O) - число + в списке операций O. Это из-за "+ 1" в факт в начале ответа - рассмотрим случай a = [1, 1, 1, 1, 1], r = 1.

В этом подходе используется O (n 2 ⁿ) время и пространство O (2 ⁿ) (где оба являются потенциально очень слабыми шкалами худших случаев). Это все еще экспоненциальный алгоритм, однако, я думаю, вы обнаружите, что он работает очень разумно для не-зловещих входов. (Я подозреваю, что эта проблема NP-полная, и именно поэтому я доволен этим предложением "не-зловещие входы".)

Ответ 2

Здесь используется подход O (rn ^ 2) -time, O (rn) -пространства. Если r < 2 ^ n, то это будет иметь лучшее худшее поведение, чем экспоненциально-временные подходы с ветвями и границами, хотя даже тогда во многих случаях последний может быть быстрее. Это псевдополиномиальное время, поскольку оно занимает время, пропорциональное значению части его ввода (r), а не его размер (который был бы log2 (г)). В частности, он требует rn бит памяти, поэтому он должен давать ответы в течение нескольких секунд до примерно rn < 1 000 000 000 и n < 1000 (например, n = 100, r = 10 000 000).

Главное наблюдение заключается в том, что любая формула, включающая все n чисел, имеет конечный член, который состоит из некоторого числа я факторов, где 1 <= я <= n. То есть любая формула должен быть в одном из следующих случаев:

• (формула на первых n-1 членах) + a [n]
• (формула на первых n-2 членах) + a [n-1] * a [n]
• (формула на первых n-3 членах) + a [n-2] * a [n-1] * a [n]
• ...
• a [1] * a [2] *... * a [n]

Позвольте называть "префикс" [], состоящий из первых я чисел P [i]. Если мы записываем для каждого 0 <= я <= n-1 полный набор значений <= r, который может быть получен по какой-либо формуле на P [i], то, основываясь на вышесказанном, мы можем довольно легко вычислить полный набор значений <= r, который может быть достигнут P [n]. В частности, пусть X [i] [j] будет истинным или ложным значением, которое указывает, может ли префикс P [i] достичь значения j. (X [] [] может быть сохранен как массив растровых изображений n size- (r + 1).) Тогда мы хотим вычислить X [n] [r], который будет истинным, если r может быть достигнуто посредством некоторая формула на [], а false в противном случае. (X [n] [r] еще не совсем полный ответ, но его можно использовать для получения ответа.)

X [1] [a [1]] = true. X [1] [j] = false для всех остальных j. Для любых 2 <= я <= n и 0 <= j <= r, мы можем вычислить X [i] [j], используя

X[i][j] = X[i - 1][j - a[i]]               ||
          X[i - 2][j - a[i-1]*a[i]]        ||
          X[i - 3][j - a[i-2]*a[i-1]*a[i]] ||
          ...                              ||
          X[1][j - a[2]*a[3]*...*a[i]]     ||
          (a[1]*a[2]*...*a[i] == j)

Обратите внимание, что последняя строка - это тест равенства, который сравнивает произведение всех i-чисел в P [i] на j и возвращает true или false. В выражении для X [i] [j] есть я <= n "terms" (rows), каждый из которых может быть вычислен в постоянное время (обратите внимание, в частности, что умножения могут быть созданы за постоянное время в строке), поэтому вычисление одного значения X [i] [j] может быть выполнено в O (n) времени. Чтобы найти X [n] [r], нам нужно вычислить X [i] [j] для каждого 1 <= я <= n и каждого 0 <= j <= r, поэтому существует O (rn ^ 2) общая работа. (Строго говоря, нам может не понадобиться вычислять все эти записи в таблице, если мы используем memoization вместо восходящего подхода, но многие входы потребуют от нас вычислить значительную часть из них в любом случае, так что, скорее всего, последнее быстрее малый постоянный коэффициент. Также подход memoization требует хранения "уже обработанного" флага для каждой ячейки DP, что удваивает использование памяти, когда каждая ячейка составляет всего 1 бит!)

Реконструкция решения

Если X [n] [r] истинно, то проблема имеет решение (удовлетворяющее формуле), и мы можем восстановить одно в O (n ^ 2) раз, проследив через таблицу DP, начиная с X [ n] [r], в каждом местоположении ищет какой-либо термин, который позволил текущему местоположению принять значение "истина" - то есть любой истинный термин. (Мы могли бы сделать этот шаг восстановления быстрее, сохранив более одного бита на (i, j) комбинацию, но так как r разрешено быть "сколь угодно большим", и эта более быстрая реконструкция не улучшит общую временную сложность, вероятно, имеет смысл идти с подходом, который использует наименьшие бит для записи в таблице DP.) Все удовлетворяющие решения могут быть восстановлены таким образом, возвращаясь через все истинные термины, а не просто подбирая любой, - но может быть экспоненциальное число из них.

ускорений

Существует два способа ускорения вычисления индивидуального значения X [i] [j]. Во-первых, поскольку все термины объединяются с ||, мы можем остановиться, как только результат станет истинным, так как более поздний термин может снова сделать его ложным. Во-вторых, если нигде слева от я нет нуля, мы можем остановиться, как только произведение конечных чисел станет больше, чем r, так как нет возможности снова уменьшить этот продукт.

Когда в [] нет нулей, эта вторая оптимизация, вероятно, будет очень важной на практике: она может сделать внутренний цикл намного меньше, чем полные итерации i-1. На самом деле, если a [] не содержит нулей, а его среднее значение равно v, то после вычисления k членов для определенного значения X [i] [j] произведение будет около v ^ k - так, в среднем, количество итераций внутреннего цикла (терминов), необходимых, падает от n до log_v (r) = log (r)/log (v). Это может быть намного меньше, чем n, и в этом случае средняя временная сложность для этой модели падает до O (rn * log (r)/log (v)).

[РЕДАКТИРОВАТЬ: Мы действительно можем сохранить умножения со следующей оптимизацией:)]

8/32/64 X [i] [j] s за раз: X [i] [j] не зависит от X [i] [k] при k!= j, поэтому, если мы используем биты для хранения этих значений, мы можем вычислить 8, 32 или 64 из них (или, может быть, больше, с SSE2 и т.д.) параллельно, используя простые побитовые операции OR. То есть мы можем вычислить первый член X [i] [j], X [i] [j + 1],..., X [i] [j + 31] параллельно, ИЛИ их в результаты, затем вычисляйте их вторичные члены параллельно и ИЛИ в них и т.д. Нам все равно нужно выполнить такое же количество вычитаний таким образом, но все продукты одинаковы, поэтому мы можем уменьшить количество умножений на коэффициент 8/32/64 - а также, конечно, количество обращений к памяти. OTOH, это делает первую оптимизацию из предыдущего абзаца более сложной задачей - вам нужно подождать, пока весь блок из 8/32/64 бит не станет истинным, прежде чем вы сможете остановить итерацию.

Zeroes: Zeroes в [] могут позволить нам остановиться раньше. В частности, если мы только что вычислили X [i] [r] для некоторого я < n и нашел, что это правда, и есть нуль в любом месте справа от позиции я в [], тогда мы можем остановиться: у нас уже есть формула для первых чисел i, которая оценивает r, и мы можем использовать это ноль, чтобы "убить" все числа справа от позиции i, создав один большой термин продукта, который включает все из них.

Ones: Интересное свойство любой записи [], содержащей значение 1, состоит в том, что его можно перемещать в любую другую позицию в [], не затрагивая, есть ли решение. Это связано с тем, что каждая удовлетворяющая формула либо имеет a * по крайней мере на одной стороне этого 1, и в этом случае она умножает некоторый другой член и не имеет никакого эффекта там и не имеет никакого эффекта нигде; или он имеет + с обеих сторон (представьте дополнительные знаки + перед первой позицией и после последнего), и в этом случае он также может быть добавлен в любом месте.

Итак, мы можем безопасно шунтировать все 1 значения до конца [], прежде чем делать что-либо еще. Дело в том, что теперь нам не нужно оценивать эти строки X [] [] вообще, потому что они влияют на результат очень просто. Предположим, что m < n в [], которые мы переместили в конец. Затем после вычисления значений m + 1 X [nm] [rm], X [nm] [r-m + 1], X [nm] [r-m + 2],..., X [nm] [r ], мы уже знаем, что X [n] [r] должно быть: если любое из них истинно, тогда X [n] [r] должно быть истинным, иначе (если все они ложные) оно должно быть ложным. Это связано с тем, что последние m могут добавлять от 0 до m в формулу по первым значениям n-m. (Но если a [] состоит полностью из 1s, то по крайней мере 1 должно быть "добавлено" - они не могут все умножить какой-либо другой термин.)

Ответ 3

Вот еще один подход, который может быть полезен. Это иногда называют алгоритмом "встреча в середине" и выполняется в O(n * 2^(n/2)). Основная идея такова. Предположим n = 40, и вы знаете, что средний слот равен +. Затем вы можете использовать все возможности N := 2^20 для каждой стороны. Пусть A будет массивом длины N, сохраняющим возможные значения левой стороны, и аналогичным образом пусть B будет массивом длины N, сохраняющим значения для правой стороны.

Затем, после сортировки A и B, нетрудно эффективно проверить, будут ли какие-либо из них суммироваться с r (например, для каждого значения в A, выполнить двоичный поиск на B > , или вы можете даже сделать это в линейном времени, если оба массива отсортированы). Эта часть занимает время O(N * log N) = O(n * 2^(n/2)).

Теперь все это предполагалось, что средний слот равен +. Если нет, то это должно быть *, и вы можете объединить два средних элемента в один (их продукт), уменьшив проблему до n = 39. Затем вы пытаетесь сделать то же самое и так далее. Если вы тщательно проанализируете это, вы должны получить O(n * 2^(n/2)) как асимптотическую сложность, так как на самом деле доминирует самый большой член.

Вам нужно сделать некоторую бухгалтерскую отчетность, чтобы на самом деле восстановить + и *, которые я упустил, чтобы упростить объяснение.