python - 如何改善算法运行时间？ cpmoptimithe不建议

我需要找到所有的组合花。花的数目只有奇数。购买金额不大于预定金额。

def bouquets(narcissus_price, tulip_price, rose_price, summ):
    count_combinations = 0
    for n in xrange(int(summ / narcissus_price) + 1):
        for t in xrange(int(summ / tulip_price) + 1):
            if n * narcissus_price + t * tulip_price > summ:
                break
            for r in xrange([1,0][(n + t) % 2], int(summ / rose_price) + 1, 2):
                if n * narcissus_price + t * tulip_price + r * rose_price > summ:
                    break
                elif (n + t + r) & 1:
                    count_combinations += 1
    return count_combinations

print bouquets(200, 300, 400, 100000) == 3524556 # large run-time

最佳答案

减少郁金香的迭代范围-而不是迭代到summ // tulip_price可以在(summ - n * narcissus_price) // tulip_price停止
您可以计算r的可能值的数目，而不必枚举它们。
例子：

def bouquets(n_price, t_price, r_price, total_price):
    """
    Count how many n, t, r (integers >= 0) exist
    such that
      n * n_price + t * t_price + r * r_price <= total_price
    and
      n + t + r is odd
    """
    count = 0

    max_n = total_price // n_price
    for n in xrange(max_n + 1):
        rem_n = total_price - n * n_price
        max_t = rem_n // t_price
        for t in xrange(max_t + 1):
            rem_t = rem_n - t * t_price
            max_r = rem_t // r_price
            min_r = (n + t + 1) % 2
            count += (max_r - min_r) // 2 + 1
    return count

在给定的测试输入上，这将运行时间从2.33s减少到67.2ms（大约快35倍）。

关于python - 如何改善算法运行时间？ cpmoptimithe不建议，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28950136/