我正在尝试解决Project Euler problem 240:
我想出了代码来解决这个问题。但是计算确实需要很多时间。我知道这种方法很糟糕。有人可以建议我如何解决此代码以使其性能更好吗？
import itertools
def check(a,b): # check all the elements in a list a, are lesser than or equal to value b
chk=0
for x in a:
if x<=b:
chk=1
return chk
lst=[]
count=0
for x in itertools.product(range(1,13),repeat=20):
a=sorted([x[y] for y in range(20)])
if sum(a[-10:])==70 and check(a[:10],min(a[-10:])):
count+=1
以下代码用于problem的描述中定义的问题。它完美地工作，并给出了确切的解决方案。
import itertools
def check(a,b):
chk=1
for x in a:
if x>b:
chk=0
break
return chk
count=0
for x in itertools.product(range(1,7),repeat=5):
a=sorted([x[y] for y in range(5)])
if sum(a[-3:])==15 and check(a[:2],min(a[-3:])):
count+=1
最佳答案
迭代所有可能性都不是一件好事，因为有1220 = 3833759992447475122176的方法来滚动20个十二面骰子，并且以每秒一百万的速度滚动，将需要数百万年的时间才能完成。
解决此类问题的方法是使用dynamic programming。寻找某种方法将您的问题分解为几个较小的问题的总和，并为这些子问题建立答案表，直到您可以计算出所需的结果为止。
例如，令T(n，d，k，t)为掷出n个d边骰子的方式数，以使它们的前k个总和为t。我们如何将其分解为子问题？好吧，我们可以考虑准确地掷出d的骰子数量i。有nCi种方法可以选择这些骰子，还有T(n−i，d-1，...)种方法可以选择剩余的n−i个骰子，这些骰子最多只能滚动d − 1(对于某些合适的参数选择对于我遗失的k和t。)
取这些乘积，然后将其求和为i的所有合适值，就可以了。 (嗯，还没做完:您必须指定基本情况，但这应该很容易。)
您需要计算的子问题数最多为(n +1)(d +1)(k +1)(t +1)，在Project Euler情况下为(n = 20，d = 12 ，k = 10，t = 70)最多为213213。(实际上，它远不止于此)，因为树的许多分支很快就可以到达基本情况:在我的实现中，结果发现只有791个子问题的答案足以计算答案。)
要编写动态程序，通常最简单的方法是递归地表达它，并使用memoization避免重新计算子问题的答案。在Python中，您可以使用 @functools.lru_cache decorator。
因此，程序的框架可能看起来像这样。我已用???替换了关键的细节，以免使您失去为自己解决它的乐趣。在尝试更大的案例之前，请使用一些小的示例(例如“两个6面骰子，其中前1个总数为6”)来检查您的逻辑是否正确。
def combinations(n, k):
"""Return C(n, k), the number of combinations of k out of n."""
c = 1
k = min(k, n - k)
for i in range(1, k + 1):
c *= (n - k + i)
c //= i
return c
@lru_cache(maxsize=None)
def T(n, d, k, t):
"""Return the number of ways n distinguishable d-sided dice can be
rolled so that the top k dice sum to t.
"""
# Base cases
if ???: return 1
if ???: return 0
# Divide and conquer. Let N be the maximum number of dice that
# can roll exactly d.
N = ???
return sum(combinations(n, i)
* T(n - i, d - 1, ???)
for i in range(N + 1))
通过为所有
???选择适当的选项，可以在几毫秒内回答Project Euler问题:>>> from timeit import timeit
>>> timeit(lambda:T(20, 12, 10, 70), number=1)
0.008017531014047563
>>> T.cache_info()
CacheInfo(hits=1844, misses=791, maxsize=None, currsize=791)