找到两个线性等式成立的整数集

Question

我可以使用什么算法来查找n1, n2, ... ,n7以下不等式成立的所有正整数值的集合.

97n1 + 89n2 + 42n3 + 20n4 + 16n5 + 11n6 + 2n7 - 185 > 0
-98n1 - 90n2 - 43n3 - 21n4 - 17n5 - 12n6 - 3n7 + 205 > 0
n1 >= 0, n2 >= 0, n3 >=0. n4 >=0, n5 >=0, n6 >=0, n7 >= 0

例如,一组n1= 2, n2 = n3 = ... = n7 =0使不等式成立.我如何找出所有其他值集？类似的问题已在M.SE中发布.

ADDED ::我需要概括n个变量的解决方案(可能很大).我可以申请什么程序？对于另一个特殊情况n=8

97n1 + 89n2 + 42n3 + 20n4 + 16n5 + 11n6 + 6n7 + 2n8 - 185 > 0
-98n1 - 90n2 - 43n3 - 21n4 - 17n5 - 12n6  - 7 - 3n8 + 205 > 0
n1 >= 0, n2 >= 0, n3 >=0. n4 >=0, n5 >=0, n6 >=0, n7 >= 0, n8 >= 0

Python需要永远.Wolfram Mathematica揭示有4015不到一分钟的解决方案.

Length[Solve[{97 n1 + 89 n2 + 42 n3 + 20 n4 + 16 n5 + 11 n6 + 6 n7 + 
     2 n8 - 185 > 0, 
   -98 n1 - 90 n2 - 43 n3 - 21 n4 - 17 n5 - 12 n6 - 7 n7 - 3 n8 + 
     205 > 0,
   n1 >= 0, n2 >= 0, n3 >= 0, n4 >= 0, n5 >= 0, n6 >= 0, n7 >= 0, 
   n8 >= 0}, {n1, n2, n3, n4, n5, n6, n7, n8}, Integers]]

Answer 1

Reti43有正确的想法,但有一个快速的递归解决方案,对你的不等式有较少的限制性假设.

def solve(smin, smax, coef1, coef2):
    """
    Return a list of lists of non-negative integers `n` that satisfy
    the inequalities,

    sum([coef1[i] * n[i] for i in range(len(coef1)]) > smin
    sum([coef2[i] * n[i] for i in range(len(coef1)]) < smax

    where coef1 and coef2 are equal-length lists of positive integers.
    """
    if smax < 0:
        return []

    n_max = ((smax-1) // coef2[0])
    solutions = []
    if len(coef1) > 1:
        for n0 in range(n_max + 1):
            for solution in solve(smin - n0 * coef1[0],
                                  smax - n0 * coef2[0], 
                                  coef1[1:], coef2[1:]):
                solutions.append([n0] + solution)
    else:
        n_min = max(0, (smin // coef1[0]) + 1)
        for n0 in range(n_min, n_max + 1):
            if n0 * coef1[0] > smin and n0 * coef2[0] < smax:
                solutions.append([n0])
    return solutions

你会把它应用到这样的原始问题上,

smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 3)
solns7 = solve(smin, smax, coef1, coef2)
len(solns7)
1013

而对于这样的长期问题,

smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 6, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 7, 3)
solns8 = solve(smin, smax, coef1, coef2)
len(solns8)
4015

在我的Macbook上,这两种情况都在几毫秒内完成.这应该可以很好地扩展到稍微大一些的问题,但从根本上说,它是系数N的O(2 ^ N).实际扩展的程度取决于附加系数的大小 - 更大的系数(与smax-相比) smin),解决方案越少,运行速度越快.

更新:从关于链接的M.SE帖子的讨论中,我看到这两个不等式之间的关系是问题结构的一部分.鉴于此,可以给出稍微简单的解决方案.下面的代码还包括一些额外的优化,可以在我的笔记本电脑上将8变量的解决方案从88毫秒加速到34毫秒.我已经尝试了多达22个变量的示例,并在不到一分钟的时间内得到了结果,但对于数百个变量来说,它永远不会实用.

def solve(smin, smax, coef):
    """
    Return a list of lists of non-negative integers `n` that satisfy
    the inequalities,

    sum([coef[i] * n[i] for i in range(len(coef)]) > smin
    sum([(coef[i]+1) * n[i] for i in range(len(coef)]) < smax

    where coef is a list of positive integer coefficients, ordered
    from highest to lowest.
    """
    if smax <= smin:
        return []
    if smin < 0 and smax <= coef[-1]+1:
        return [[0] * len(coef)]

    c0 = coef[0]
    c1 = c0 + 1
    n_max = ((smax-1) // c1)
    solutions = []
    if len(coef) > 1:
        for n0 in range(n_max + 1):
            for solution in solve(smin - n0 * c0,
                                  smax - n0 * c1, 
                                  coef[1:]):
                solutions.append([n0] + solution)
    else:
        n_min = max(0, (smin // c0) + 1)
        for n0 in range(n_min, n_max + 1):
            solutions.append([n0])
    return solutions

您可以将它应用于这样的8变量示例,

solutions = solve(185, 205, (97, 89, 42, 20, 16, 11, 6, 2))
len(solutions)
4015

该解决方案直接列举有界区域中的晶格点.由于您需要所有这些解决方案,因此获取它们所需的时间将与绑定的网格点的数量成比例(最多),这些网格点随着维度(变量)的数量呈指数增长.