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

Question

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

Answer 1

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

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

当然有很多，但是10个！其中一些仍然可以通过计算机进行管理。

编辑：OP 已编辑问题，因此：数字 10 应分为最多 10 个部分的整数分区，其中每个部分最多 2 个。

Answer 2

如果你真的想要所有的解决方案：通过一些优化递归枚举所有可能的变量赋值：

最后一个变量的值可以从求和约束中计算出来
当您发现部分赋值不再能够得出有效的解决方案时（例如，如果总和已经大于 10，或者剩余的变量太少而无法达到 10 的总和），可以删减搜索)

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)

如果选择return方案，即可以如下：

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)

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

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

how to find all integer solutions to sum(xi) =b, with linear constraints

algorithm

equation-solving

integer-programming