這是一個益智題,但如果要從純粹計算的角度來完成,那麼窮舉可能是題主想要的結果。
題主的代碼實作了随機選擇政策,然後直到選出一個滿足要求的答案就退出了程式。
如果在題主的代碼裡修改,主要改進兩點。周遊所有可能的過河政策
在周遊過程中避免對重複的政策重新計算
前者可以求出“最快幾秒過橋”,後者提高性能。
下面的代碼是在問題中原有邏輯上改的,這不是最好的(有點醜),但是可能更直覺點。(去除重複政策沒有在程式中展現。)
在每個函數裡打打目前的 a / b 日志,有助于發現到底有哪些組合。
最後的 result 隻記錄了可能的過河時間,最快也需要 29 秒。
import itertools
def calcu_from(a, b):
'''
在目前 a / b 情況下,計算從 A -> B 所有可能的過河時間
'''
result = set()
for step in itertools.combinations(a, 2):
m = max(step)
tmp_b = b[:]
tmp_b.extend(step)
next = calcu_to([e for e in a if e not in step], tmp_b)
for n in next:
result.add(n + m)
return result
def calcu_to(a, b):
'''
在目前 a / b 情況下,計算從 B -> A 所有可能的過河時間
'''
if len(a) == 0:
return set([0])
result = set()
for step in itertools.combinations(b, 1):
m = step[0]
tmp_a = a[:]
tmp_a.extend(step)
next = calcu_from(tmp_a, [e for e in b if e not in step])
for n in next:
result.add(n + m)
return result
a = [1, 3, 6, 8, 12]
b = []
result = calcu_from(a, b)
print(result)