http://www.gecode.org/ http://minion.sourceforge.net/ http://jacop.osolpro.com/ http://research.microsoft.com/apps/pubs/default.aspx?id=64335
这是维基百科的列表：
N > 100，找到所有解决方案会变得非常缓慢，但我看不到另一种能很好地处理大N值的方法。 :( - ruifrom math import floor, ceil
def iter_solutions(r, n, z):
c = [None] * n
def iter_solutions_bounded(k, pick):
# pick is the last pick, if any, and 0 otherwise
assert (1 <= k < n and pick == c[k]) or (k == n and pick == 0)
min_ck = int(ceil(-pick / r))
max_ck = int(floor((z - pick) / r))
if k == 1:
for ck in range(max(min_ck, 0), min(max_ck, z) + 1):
c[0] = ck
yield c
else:
for ck in range(min_ck, max_ck + 1):
c[k - 1] = ck
for soln in iter_solutions_bounded(k - 1, ck):
yield soln
return iter_solutions_bounded(n, 0)
你可以将这个转化为仅仅 计数 解决方案的代码，只需删除所有涉及到 c 的代码，并累加产生的解决方案数量即可。最后，你可以通过记忆化来提高性能。
from math import floor, ceil
def memoize(f):
cache = {}
def g(*args):
if args in cache:
return cache[args]
tmp = cache[args] = f(*args)
return tmp
return g
def len_range(a, b):
if a <= b:
return b - a
return 0
def count_solutions(r, n, z):
@memoize
def count_solutions_bounded(k, pick):
min_ck = int(ceil(-pick / r))
max_ck = int(floor((z - pick) / r))
if k == 1:
return len_range(max(min_ck, 0), min(max_ck, z) + 1)
else:
return sum(count_solutions_bounded(k - 1, ck) for ck in range(min_ck, max_ck + 1))
return count_solutions_bounded(n, 0)
一些可能的改进：
如果确保 c1 ... cn 始终≤ z，那么检测并立即返回0将对大的n非常有帮助。事实上，它将把运行时间降至闪电般快速的O(nz)。
如果c1 ... cn都为非负数，则更好。对min_ck和max_ck进行适当的更改，可以使其O（nz）具有较小的常数，并且缓存可以是平面的2D数组，而不是我现在使用的较慢的哈希表。
通过系统地构建缓存，而不是像此记忆化代码一样“按需”填充它，您可能会做得更好。首先为n=1建立整个缓存，然后为n=2建立，以此类推。那样，你可以避免递归，并在每个步骤中丢弃你不再需要的缓存数据（在计算n=2的结果之后，你不再需要n=1的条目）。
这并不是你问题的完整解决方案，但我认为它可能会有所帮助或者至少给你一些想法。
你要求解的整数解使得这个问题成为了一个NP问题。如果我们首先考虑放松问题，使得定义域为实数，那么你要求解的就是满足0 <= A*c <= 1的可满足性问题，其中A是矩阵，c是未知向量。这是一个标准的线性规划问题（带有微不足道的目标），可以高效地解决（在多项式时间内）。你可以将其用作第一次通过测试以确定可行性，因为如果放松后的线性规划没有解，那么你的整数线性规划肯定也没有解。一个好的线性规划求解器还会返回一个可行点，如果可能的话，你可以四舍五入向量的条目以找到一个整数解。
正如其他人所提到的，如果你想要基于这些约束条件最大化一个线性目标函数，那么你会有一个整数线性规划问题，对于这种问题，不存在有效的通用解决方案。相反，你似乎正在询问可行区域中点的数量，这是一个不同的问题，但它也因为必须具有整数解而变得复杂。
我能想到的最好的主意是找到可行区域边界上的点，并使用它们来确定内部的点数。在低维度下，这可以加速“计算格点”的类型问题，但是边界仍然比涉及的体积小一个维度。如果你的问题超过了几个维度，那么即使它比枚举所有解决方案更快，问题仍然难以处理。
r是什么？（由于某种原因，注释需要至少15个字符。） - Svante