我正在嘗試解決以下問題：A store sells large individual wooden letters for signs to put on houses. The letters are priced individually.The total cost of letters in LOAN is 17 dollars.The total cost of letters in SAM is 18 dollars.The total cost of letters in ANNA is 20 dollars.The total cost of letters in ROLLO is 21 dollars.The total cost of letters in DAMAGES is 30 dollars.The total cost of letters in SALMON is 33 dollars.How much would the letters in the name GARDNER cost?我使用以下 python 代碼強制執行字母成本，但需要幾個小時才能收斂，因為它們有 33^10 個可能的組合來測試。我使用 n=33，因為它是名稱的最大成本，但確實，n 可以減少到 15 甚至 10，但如果不保證它會收斂。def func(letters): print letters if letters['L']+letters['O']+letters['A']+letters['N'] != 17: return False elif letters['S']+letters['A']+letters['M'] != 18: return False elif 2*letters['A']+2*letters['N'] != 20: return False elif letters['R']+2*letters['O']+2*letters['L'] != 21: return False elif letters['D']+2*letters['A']+letters['M']+letters['G']+letters['E']+letters['S'] != 30: return False elif letters['S']+letters['A']+letters['L']+letters['M']+letters['O']+letters['N'] != 33: return False return Truedef run(letters, n, forbidden_letters): for letter in letters.keys(): if letter not in forbidden_letters: for i in range(1, n): letters[letter] = i if not func(letters): if letter not in forbidden_letters: forbidden_letters+=letter if run(letters, n, forbidden_letters): return letters else: return lettersLETTERS = { "L":1, "O":1, "A":1, "N":1, "S":1, "M":1, "R":1, "D":1, "G":1, "E":1,}n=33print run(LETTERS, n, "")暴力破解最終會奏效，但它占用的 CPU 資源如此之多，以至于它肯定不是最佳解決方案。有沒有人有更好的解決方案來解決這個問題？要么通過減少計算時間，要么通過良好的數學方法。謝謝大家。
2 回答
叮當貓咪
TA貢獻1776條經驗 獲得超12個贊
這就是所謂的線性方程組。如果需要，您可以手動解決這個問題，但您也可以使用線性求解器。例如與同情
import sympy
l,o,a,n,s,m,r,d,g,e = sympy.symbols('l,o,a,n,s,m,r,d,g,e')
eq1 = l+o+a+n - 17
eq2 = s+a+m -18
eq3 = a+n+n+a -20
eq4 = r+o+l+l+o -21
eq5 = d+a+m+a+g+e+s -30
eq6 = s+a+l+m+o+n- 33
sol, = sympy.linsolve([eq1,eq2,eq3,eq4,eq5,eq6],(l,o,a,n,s,m,r,d,g,e))
l,o,a,n,s,m,r,d,g,e = sol
print(g+a+r+d+n+e+r)
線性方程的求解速度非?？?。復雜度為 O(n 3 )，其中 n 是變量的數量。所以對于這樣一個小問題，它幾乎是即時的。
MYYA
TA貢獻1868條經驗 獲得超4個贊
L + O + A + N - 17 = 0
S + A + M - 18 = 0
2 * A + 2 * N - 20 = 0
等等。
嘗試制作一個矩陣，如：
L O A N S M R D G E val
[1 1 1 1 0 0 0 0 0 0 -17 | 0] LOAN
[0 0 1 0 1 1 0 0 0 0 -18 | 0] SAM
[0 0 2 2 0 0 0 0 0 0 -20 | 0] ANNA
...
[0 0 1 1 0 0 2 1 1 2 -x | 0] GARDENER
現在您可以使用例如高斯方法來解決它。這將需要 O(n^3) 時間復雜度。
添加回答
舉報
0/150
提交
取消