Алгоритм подмножества-суммы с вычитанием

Я думаю, что ваша идея в основном верна: сгенерируйте каждую комбинацию терминов, подсчитайте сумму и посмотрите, сработает ли она. Однако вы можете оптимизировать свой код.

Проблема в том, что как только вы сгенерируете 1 + 2, вы увидите, что это не соответствует желаемой сумме, и выбросите ее. Однако, если вы добавите к нему 4, это решение. Вы не доберетесь до этого решения, пока не сгенерируете 1 + 2 + 4, когда будете вычислять сумму с нуля. Вы также создаете возможности добавления операторов с нуля для каждой комбинации, что по той же причине выполняет много избыточной работы.

Вы также используете много операций со списками, которые могут быть медленными.

я бы сделал так:

def solve(terms_list, stack, current_s, desired_s):
    if len(terms_list) == 0:
        if current_s == desired_s:
            print(stack)
        return

    for w in [0, 1, -1]: # ignore term (0), add it (1), subtract it (-1)
        stack.append(w)
        solve(terms_list[1:], stack, current_s + w * terms_list[0], desired_s)
        stack.pop()

Начальный вызов, например, solve([1,2,3,4,5], [], 0, 7).

Обратите внимание, что это имеет сложность O(3^n) (вроде как, читайте дальше), потому что каждый термин можно добавить, вычесть или проигнорировать.

Сложность моей фактической реализации O(n*3^n), потому что рекурсивный вызов делает копию параметра terms_list. Однако этого можно избежать, но я хотел упростить код и оставить это в качестве упражнения. Вы также можете не строить фактическое выражение перед его печатью и создавать его постепенно, но для этого вам может понадобиться больше параметров.

Тем не менее, O(3^n) все равно много, и не стоит ожидать, что он будет хорошо работать при больших n, что бы вы ни делали.

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

f(0,i) = 1               //successive subset
f(x,0) = 0    x>0        //failure subset
f(x,i) = f(x+element[i],i-1) + f(x-element[i],i-1) + f(x,i-1)
                                 ^^^
               This is the added option for substraction

При переводе его в восходящее решение DP вам нужно будет создать матрицу размера (SUM+1) * (2n+1), где SUM — сумма всех элементов, а n — количество элементов.

Прямо сейчас вы пытаетесь перебрать все возможные комбинации значений полей из одной строки (затем проверить достоверность каждой комбинации по сравнению с другими строками).

Я предполагаю, что у вас есть много строк данных для игры; Я предлагаю вам воспользоваться этим, взяв кучу строк (по крайней мере, столько, сколько у вас есть полей для решения) и применив приближенный матричный решатель, такой как numpy.linalg.lstsq.

Это имеет ряд важных преимуществ:

• позволяет разумно справляться с проблемами ошибок округления (необходимо, если какое-либо из ваших полей не является целым числом)

• позволяет вам легко обрабатывать поля, коэффициент которых не находится в {-1, 0, 1}, т. е. налоговые ставки, коэффициент которых может быть чем-то вроде 0.12

• использует полностью поддерживаемый код, который вам не нужно отлаживать или поддерживать

• использует высокооптимизированный код, который будет работать значительно быстрее (** скорее всего, в зависимости от того, с какими опциями был скомпилирован ваш numpy)

• имеет безумно лучшую временную сложность (что-то вроде O (n ** 2,8) вместо O (3 ** n)), что означает, что он должен масштабироваться до значительно большего количества полей.

Итак, некоторые тестовые данные:

import numpy as np

# generate test data
def make_test_data(coeffs, mean=20.0, base=0.05):
    w      = len(coeffs)    # number of fields
    h      = int(1.5 * w)   # number of rows of data
    rows   = np.random.exponential(mean - base, (h, w)) + base
    totals = data.dot(coeffs)
    return rows.round(2), totals.round(2)

что дает нам что-то вроде

>>> rows, totals = make_test_data([0, 1, 1, 0, -1, 0.12])

>>> print(rows)
[[  1.45  17.63  22.54   5.54  37.06   1.47]
 [ 11.71  80.43  26.43  18.48  11.08   8.8 ]
 [ 16.09  11.34  63.74   3.31  13.2   13.35]
 [ 11.96  12.17  10.23   8.15  73.3    0.42]
 [  4.03   8.01  20.84  21.46   2.76  18.98]
 [  3.24   6.6   35.06  23.17   9.03   8.58]
 [ 25.05  33.72   6.82   0.49  46.76  12.21]
 [ 70.27   1.48  23.05   0.69  31.11  43.13]
 [  9.04  10.45  15.08   4.32  52.94  11.13]]

>>> print(totals)
[  3.29  96.84  63.48 -50.85  28.37  33.66  -4.75  -1.4  -26.07]

и код решателя,

>>> sol = np.linalg.lstsq(rows, totals)    # one line!

>>> print(sol[0])       # note the solutions are not *exact*
[ -1.485730e-04  1.000072e+00  9.999334e-01 -7.992023e-05 -9.999552e-01  1.203379e-01]

>>> print(sol[0].round(3))      # but they are *very* close
[ 0.    1.    1.    0.   -1.    0.12]