如何改进我的算法运行时间？ cpoptimithe 不建议

Question

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

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

Answer 1

• 减少郁金香的迭代范围 - 您可以在 (summ - n * narcissus_price) // tulip_price
处停止而不是迭代到 summ // 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.33 秒减少到 67.2 毫秒（大约快 35 倍）。