python - 找出数字组合中的最大和

Question

可以说我有这个：

1A=6 2A=4.5  3A=6

1B=7 2B=6    3B=7.5

1C=6 2C=6.75 3C=9

我想找到产生最高总和的数字组合。字母前面的数字不能使用超过一次，数字后面的字母不能多次使用。例如。1A+2B+3C, 1C+2B+3A是有效的。1A+1B+2B,3A+2B+3B,1A+2A+3A无效。

在这种情况下，最高和是1A+2B+3C=21。我如何使用 python 找到这个结果和组合？

提前致谢

Answer 1

对于具有相同数字前缀的每个条目，找出其中的最大值。然后将所有这些最大值相加，您将得到具有给定限制的最大和。

如果数字和字母必须是唯一的，那么它就成为一个可以用匈牙利算法解决的问题。

匈牙利方法是一种组合优化算法，在多项式时间内解决分配问题[...]

从分配问题的描述：

赋值问题是数学优化或运筹学分支中的基本组合优化问题之一。它包括在加权二分图中找到最大权重匹配。

以最一般的形式，问题如下：

有许多代理和许多任务。可以分配任何代理来执行任何任务，产生的成本可能会因代理任务分配而异。需要通过为每个任务准确分配一个代理并为每个代理准确分配一个任务来执行所有任务，以使分配的总成本最小化。

Answer 2

我不是 python 人，所以下面的代码可能看起来不是“python 风格”，但算法应该没问题。

#test input. the matrix can be any n * n size.
matrix = [[6,7,6],[4.5,6,6.75],[6,7.5,9]]

#assistant array to track which numbers we have already used.
#check[i] = 1 if i has been used
check = [0]* len(matrix)

#max sum
max_sum = 0

def getMax(matrix,check,row,curr_sum):
    global max_sum
    #base case, we have reached the last letter.
    #check to see if this combination is max
    if(row==len(matrix)-1):
        for i in range(len(check)):
            if(check[i]==0 and (matrix[row][i]+curr_sum)>max_sum):
                max_sum = matrix[row][i]+curr_sum
    #recursive case, pick the current available number, go to next letter.
    else:
        for i in range(len(check)):
            if(check[i]==0):
                check[i]=1
                getMax(matrix,check,row+1,curr_sum+matrix[row][i])
                check[i]=0

getMax(matrix,check,0,0)

print max_sum

请注意，这是一种使用递归的蛮力算法。在时间复杂度方面，存在更好的算法（例如动态规划方法）。您可以在方法中添加缓存以提高效率。

此外，如果您想知道组合，我们需要额外的努力来跟踪组合。（例如使用另一个矩阵来记录）

Answer 3

这可以通过以下方式完成：

l1 = [6, 7, 6]
l2 = [4.5, 6, 6.75]
l3 = [6, 7.5, 9]

map(max, [l1, l2, l3])

Answer 4

实际上，python 有可以为您执行此操作的库。见这里：芒克雷斯