python - 带减法的子集求和算法

Question

我有一个子集求和问题，您可以在其中添加或减去项。例如，如果我有五个项(1、2、3、4、5)，我想知道有多少种方法可以加/减这些项以得到 7:

• 3 + 4
• 2 + 5
• 1 + 2 + 4
• 5 - 2 + 4
• 等等

我用Python写了一些代码，但是一旦有很多术语就很慢:

import itertools
from collections import OrderedDict

sum_answer = 1
terms = {"T1": 1, "T2": -2, "T3": 3, "T4": -4, "T5": 5}
numlist = [v for v in terms.values()]
zerlist = [x for x in itertools.repeat(0, len(numlist))]
opslist = [item for item in itertools.product((1, -1), repeat=len(numlist))]


res_list = []
for i in range(1, len(numlist)):
    combos = itertools.combinations(numlist, i)

    for x in combos:
        prnlist = list(x) + zerlist[:len(numlist) - len(x)]

        for o in opslist:
            operators = list(o)
            result = []
            res_sum = 0

            for t in range(len(prnlist)):
                if operators[t] == 1:
                    ops = "+"
                else:
                    ops = "-"
                if prnlist[t] != 0:
                    result += [ops, list(terms.keys())[list(terms.values()).index(prnlist[t])]]
                res_sum += operators[t] * prnlist[t]

            if sum_answer == res_sum:
                res_list += [" ".join(result)]

for ans in OrderedDict.fromkeys(res_list).keys():
    print(ans)

我意识到一百万个嵌套循环的效率非常低，那么我可以使用更好的算法加快任何部分的速度吗？

Answer 1

类似于“常规”子集求和问题 - 使用 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 是元素的数量。