从两个集合中选择一个数字，每个集合的乘法和等于一个特定的和

Question

我有两个集合，比如A={0,1,2，…，I}和B={3,6,10,15}，一个常量$s$，和一个属于自然数集合的指定数$n$。 我想找到满足a_1*b_1+a_2*b_2+\dots+a_n*b_n>；=s的a/all组合

例如，如果s=25，n=2，则以下每个答案都是可接受的1*10+1*15、2*10+1*6、0+2*15或4*3+2*6

如果没有第二个集合，那就很容易了，因为问题归结为生成具有预定和s的随机分区，如here中介绍的那样

我应该如何在python中有效地实现这一点？有什么数学方法吗？ 它也让我想起了某种等式，但我不确定我应该寻找什么。 我很感激任何暗示。你知道吗

编辑：对我来说，在我的答案中准确地用“n”字眼是很重要的，而且还有其他选择的机会。在我的例子中，四个答案中的每一个都应该有机会产生。换言之，我有“n”的地方来填充它们，使它们的和等于“s”。很抱歉，一开始没有澄清。你知道吗

Answer 1

它可以通过直接的递归来实现。你知道吗

from functools import lru_cache

def find_combinations(numbers, threshold, nterms, maxcoeff, stringify=True):
    numbers = sorted(numbers, reverse=True)
    @lru_cache(None)
    def rec(k, s, n):
        if s > maxcoeff * numbers[k]:
            top = maxcoeff
            res = []
        else:
            top = (s-1) // numbers[k]
            res = [[top + 1]]
        if n > 1 and k < len(numbers)-1:
            for j in range(top, -1, -1):
                res.extend([[j, *subres] for subres in rec(
                    k+1, s-j*numbers[k], n-(j!=0))])
        return res
    if stringify:
        return [' + '.join(f'{c}\u2a2f{n}' for c, n in zip(sol, numbers) if c)
                for sol in rec(0, threshold, nterms)]
    else:
        return rec(0, threshold, nterms)

print(find_combinations({3, 6, 10, 15}, 25, 2, 2))

印刷品：

['2⨯15', '1⨯15 + 1⨯10', '2⨯10 + 1⨯6']

更新：允许numbers多次occcur（这些是集中在一起的，基本上maxcoeff乘以每个数字的出现次数）：

def find_combinations_with_replacement(numbers, threshold, nterms, maxcoeff,
                                       stringify=True):
    numbers = sorted(numbers, reverse=True)
    @lru_cache(None)
    def rec(k, s, n):
        if s > maxcoeff * numbers[k] * n:
            return []
        top = (s-1) // numbers[k]
        res = [[top + 1]]
        if n > 1 and k < len(numbers)-1:
            for j in range(top, -1, -1):
                res.extend([[j, *subres] for subres in rec(
                    k+1, s-j*numbers[k], n - (j-1) // maxcoeff - 1)])
        return res
    if stringify:
        return [' + '.join(f'{c}\u2a2f{n}' for c, n in zip(sol, numbers) if c)
                for sol in rec(0, threshold, nterms)]
    else:
        return rec(0, threshold, nterms)

print(find_combinations_with_replacement({3, 6, 10, 15}, 25, 4, 1))

印刷品：

['2⨯15', '1⨯15 + 1⨯10', '1⨯15 + 2⨯6', '1⨯15 + 1⨯6 + 2⨯3', '3⨯10', '2⨯10 + 1⨯6', '2⨯10 + 2⨯3', '1⨯10 + 3⨯6', '1⨯10 + 2⨯6 + 1⨯3']