algorithm - 对总和有限制的安排

Question

我正在寻找一种算法，它给出了给定步骤 S(可以是正实数)的 n 个序列的重复排列，条件是所有组合的总和为 k，其中 k 为正整数。

因此，我的问题是找到方程的解:

x 1 + x 2 +⋯+ x n = k在哪里

0 ≤ x i ≤ b iS(步长)是有限小数的实数。

例如，如果 0≤xi≤50，且 S=2.5，则 xi = {0, 2.5 , 5,..., 47.5, 50}。

这里的要点是只查看 sum=k 的组合，因为如果 n 很大，就不可能生成所有排列，所以我想绕过它，只生成与约束匹配的组合。

例如，我想从 n=2 开始，找到所有符合约束条件的线性组合。

例如:如果 xi = {0, 2.5 , 5,..., 47.5, 50} 并且 k=100，那么我们只有一个组合={50,50}对于 n=3，我们有 n=2 乘以 3 的组合，即 {50,50,0}、{50,0,50} 和 {0,50,50} 加上组合 {50,47.5,2.5} * 3!等等……

如果 xi = {0, 2.5 , 5,..., 37.5, 40} 且 k=100，则 n=2 有 0 种组合，因为 2*40<100，并且我们有 {40,40, 20} 次 3 对于 n=3...(如果我没记错的话)

我有点迷茫，因为我似乎找不到启动算法的正确方法，知道我应该将步骤 S 和 b 作为输入。

你有什么建议吗？

谢谢

Answer 1

您可以通过将所有内容除以 S 将您的问题转化为整数问题:我们想要找到所有整数序列 y₁, ..., y _n 有:

(1) 0 ≤ y_i ≤ ⌊b / S⌋

(2) y₁ + ... + y_n = k / S

我们可以看到，如果k 不是S 的倍数，则无解。一旦我们减少了问题，我建议使用伪多项式动态规划算法来解决 subset sum problem然后从中重建解决方案。设 f(i, j) 是用 i 元素求和 j 的方法数。我们有以下重复:

f(0,0) = 1
f(0,j) = 0  forall j > 0
f(i,j) = sum_{m = 0}^{min(floor(b / S), j)} f(i - 1, j - m)

我们可以通过逐行填充来在O(n * k/S) 时间内解决f。现在我们要重建解决方案。我正在使用 Python 风格的伪代码来说明这个概念:

def reconstruct(i, j):
    if f(i,j) == 0: 
        return
    if i == 0:
        yield []
        return
    for m := 0 to min(floor(b / S), j):
        for rest in reconstruct(i - 1, j - m):
             yield [m] + rest

result = reconstruct(n, k / S)

result 将是所有可能组合的列表。