algorithm - 线性不等式的计数解

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
我试图解决一个问题，我已经减少到计数的整数解决方案的一些线性不等式。我需要能够计算任意数量变量c_1，…，c_n的解的数量，但是对于n=3，方程可以写成：
The equations. http://silicon.appspot.com/readdoc?id=155604
现在，我预先知道N和R的值，并希望找到存在的（Cy1，…，Cyn）解的数目。
这样做是否有效（比枚举解决方案更快）？（如果是：怎么做？；如果不是：为什么？）

最佳答案

假设您有一些代码来生成所有的解决方案。
（对于这里的参数z，传递9。这是不等式右边的数字请注意，此代码仅在r为正时有效。）

from 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的条目）。

关于algorithm - 线性不等式的计数解，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1970507/