如何改进算法运行时？CPM不建议

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 // 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.33秒缩短到67.2毫秒（大约快35倍）。在