algorithm - 子集和变化

Question

给定一个整数 n 和 s 不同大小的集合，但是从 0 到 s_i 作为元素。在这里将一个好的总和定义为 a_1 + a_2 + ... + a_s = n。当您为每个 a_i 从其对应的集合 s_i 中取出一个元素时，计算存在多少总和。

我尝试生成任何可能的方式并省略那些可省略的方式，即当你有例如 s=3、n=1 并且你得到了集合s_0={0,1}, s_1={0,1,2,3}, s_2={0,1,2} ，那么您可以省略对总和 0 + 0 + a_3 的检查，因为 a_3 不够大。 我已经为每个可能的序列应用了正常子集总和的动态规划解决方案，但是，我得到的结果比我应该得到的要大得多，而且速度也很慢。

有什么好的算法可以在这里应用吗？

Answer 1

您可以通过使用两个字典(数组也可以，但字典更好)对经典的子集求和解决方案进行细微的改动:

dp[i] = dictionary of sums we can obtain using the first i sets and their counts


dp[0, <elements in s[0]>] = 1
for i = 1 to s - 1:
  for each element x in dp[i - 1]:
    for each element k in s[i]:
      dp[i, x + k] += dp[i - 1, x]

复杂性会非常大，但我认为您无能为力。不过应该可以。

你可以只在内存中保留两个字典，因为你只需要当前和以前的字典。

Python代码:

def solve(s, n):

    dp = [dict()] * len(s)

    for k in s[0]:
        dp[0][k] = 1
    for i in range(1, len(s)):
        dp[i] = dict()
        for x in dp[i - 1]:
            for k in s[i]:
                if x + k in dp[i]:
                    dp[i][x + k] += dp[i - 1][x]
                else:
                    dp[i][x + k] = dp[i - 1][x]

    return dp[len(s) - 1][n]

print(solve([[0,1,2],[0,1,2]], 3)) # prints 2
print(solve([[0,1,2],[0,1,2,3,4],[0,1,2,3,4]], 5)) # prints 13