给定一个整数 N 和取值套不同大小的，但积极的升序编号，从 0 到 S_I 的元素。让一个很好的总和在这里被定义为 A_1 + A_2 + ... + A_S = N 。指望有多少款项是存在的，当你把每一个 A_I 从它的元素所对应的设置 S_I 。

Given an integer n and s sets of different sizes, but with positive ascending numbers from 0 to s_i as elements. Let a good sum be defined here as a_1 + a_2 + ... + a_s = n. Count how many sums are existent, when you take for every a_i an element from it's corresponding set 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 将不能够足够大。 我已经申请了正常的子集和动态规划解决方案，为每个可能的序列，但是，我得到更大的成绩比我要和它的很慢了。

I tried to generate any possible way and omit those which are omittable, i.e. when you have for example s=3, n=1 and you are given the sets s_0={0,1}, s_1={0,1,2,3}, s_2={0,1,2}, then you can omit the check for the sum 0 + 0 + a_3 since a_3 won't be able to be large enough. I've applied the dynamic programming solution for normal subset sum for each of those possible sequences, however, I get much larger results than I should and its very slow, too.

有没有我可以在这里申请任何好的算法？

Are there any good algorithms which I can apply here?

推荐答案

您可以实现对经典的子集和解决方案的轻微变化，通过使用两个字典（阵列还可以工作，但字典是更好）：

You could implement a slight variation on the classical subset sum solution, by using two dictionaries (arrays can also work, but dictionaries are nicer):

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]

复杂性将是相当大的，但有没有什么可以做，以减少它，我觉得。它应该工作，虽然。

Complexity will be quite large, but there's not much you can do to reduce it I think. It should work though.

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

You can get away with only keeping two dictionaries in memory, because you only need the current and the previous ones.

Python的code：

Python code:

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