algorithm - 如何使用线性约束找到 sum(xi) =b 的所有整数解

Question

假设 sum(xi) = 10, 0<= xi <= 2, i = 1, 2, ..., 10。如何找到 xi 的所有整数解。谢谢你。我已经阅读了欧几里得算法，但它看起来只是两个未知变量。这里可以使用什么算法。

Answer 1

如果您真的想拥有所有解决方案：递归枚举所有可能的变量赋值并进行一些优化：

1. 最后一个变量的值可以从总和约束中计算出来
2. 当您看到部分分配不再导致有效的解决方案时（例如，如果总和已经大于 10 或者如果剩下的变量太少而无法达到总和 10），则可以修剪搜索

Answer 2

您正在寻找数字 100 的整数分区的排列，其中每个整数分区都有

• 最多10个部分；和
• 每个部分最多 15 个。

肯定有很多案例，但10个！其中仍然可以通过计算机进行管理。

编辑：OP已经编辑了这个问题，所以：数字10应该分成最多10个部分的整数分区，每个部分最多2个。

Answer 3

递归是最好的。这是带有生成器的自然 Python 解决方案：

def solutions(variables, sum_left, max_value):
    if 0 == variables:
        if 0 == sum_left:
            yield []
    else:
        for i in range(0, max_value + 1):
            if sum_left < i:
                break
            else:
                for partial_solution in solutions(variables - 1, sum_left - i,
                                                  max_value):
                    yield [i] + partial_solution

for x in solutions(10, 10, 2):
    print(x)

生成器的好处是您不必先在内存中构建长列表。这是一个不使用生成器并且也避免建立列表的替代解决方案。

def do_something_for_solutions(variables, sum_left, max_value, known=None):
    if known is None:
        known = []
    if 0 == variables:
        if 0 == sum_left:
            do_something(known)
    else:
        for i in range(0, max_value + 1):
            if sum_left < i:
                break
            else:
                do_something_for_solutions(variables - 1, sum_left - i,
                                           max_value, known + [i])

def do_something(solution):
    print(solution)

do_something_for_solutions(10, 10, 2)

如果您选择返回解决方案，则可能如下：

def solutions(variables, sum_left, max_value):
    if 0 == variables:
        if 0 == sum_left:
            return [[]]
        else:
            return []
    else:
        answer = []
        for i in range(0, max_value + 1):
            if sum_left < i:
                break
            else:
                for partial_solution in solutions(variables - 1, sum_left - i,
                                                  max_value):
                    answer.append([i] + partial_solution)
        return answer

for x in solutions(10, 10, 2):
    print(x)

（请注意，如果您更改参数，该列表很容易变得庞大......）