如何在不使用暴力和/或大量计算时间的情况下解决这个问题？

Question

我正在尝试解决以下问题：

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 True

def 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 letters

LETTERS = {

    "L":1,

    "O":1,

    "A":1,

    "N":1,

    "S":1,

    "M":1,

    "R":1,

    "D":1,

    "G":1,

    "E":1,

}

n=33

print run(LETTERS, n, "")

暴力破解最终会奏效，但它占用的 CPU 资源如此之多，以至于它肯定不是最佳解决方案。

有没有人有更好的解决方案来解决这个问题？要么通过减少计算时间，要么通过良好的数学方法。

谢谢大家。

Answer 1

这就是所谓的线性方程组。如果需要，您可以手动解决这个问题，但您也可以使用线性求解器。例如与同情import sympyl,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 - 17eq2 = s+a+m -18eq3 = a+n+n+a -20eq4 = r+o+l+l+o -21 eq5 = d+a+m+a+g+e+s -30eq6 = s+a+l+m+o+n- 33sol, = 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 = solprint(g+a+r+d+n+e+r)线性方程的求解速度非常快。复杂度为 O(n 3 )，其中 n 是变量的数量。所以对于这样一个小问题，它几乎是即时的。

Answer 2

L + O + A + N - 17 = 0S + A + M - 18 = 02 * 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) 时间复杂度。