我可以使用哪种算法来找到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中。添加:: 我需要归纳n个变量的解决方案(可能很大)。我可以申请什么程序？对于，另一个特殊情况
n=897n1 + 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]]
最佳答案
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 post的讨论中，我看到这里两个不等式之间的关系是问题结构的一部分。鉴于此，可以给出一个稍微简单的解决方案。下面的代码还包括几个其他的优化，可以将笔记本电脑上的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
该解决方案直接枚举有界区域中的晶格点。由于您需要所有这些解决方案，因此获得这些解决方案所需的时间(最多)与绑定(bind)晶格点的数量成比例，该数量随尺寸(变量)的数量呈指数增长。