子集和变化

Question

给定一个不同大小的整数< code>n和< code>s集合，但元素为从< code>0到< code>s_i的正升序数字。让一个好的和在这里被定义为...a_s = n。当您从对应的集合< code>s_i中为每个< code>a_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