从Matrix获得最高总和的最佳方法(使用Java但算法是这里的问题)

Question

对不起,我不知道使用的正确术语,但我有一个像这样的3x3矩阵

1 3 4 
5 4 5  
2 2 5  

我希望通过从每一行/列中选择一个值来获得最高分,但我不能多次选择相同的行或列,所以这种情况下的答案是

3 + 5 + 5 = 13(row0,col1 + row1,col0 + row2,col2)

不允许4 + 5 + 5 = 14,因为它会从col2中选择两个值

我正在使用Java,通常矩阵的大小为15 x 15.

是否有我试图做的名称,以及算法是什么

谢谢保罗

编辑:注意:匈牙利算法只有在没有行等于没有cols的情况下才有效,而在我的情况下,情况并非总是如此,我经常会遇到10x12或11x13的情况.但是看起来你可以通过添加额外的虚拟行来绕过它.

编辑嗯,尝试其中一个implmentations并没有alwasy似乎工作,除非我误读它

100.0,100.0,100.0,100.0,30.0,80.0,80.0,100.0,100.0,80.0,
80.0,100.0,100.0,100.0,80.0,80.0,25.0,100.0,100.0,80.0,
80.0,100.0,100.0,100.0,80.0,25.0,80.0,100.0,100.0,80.0,
100.0,25.0,80.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,
0.0,100.0,100.0,100.0,100.0,80.0,80.0,100.0,100.0,100.0,
100.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,25.0,100.0,
100.0,100.0,100.0,25.0,100.0,100.0,100.0,75.0,100.0,100.0,
100.0,80.0,30.0,100.0,75.0,100.0,100.0,100.0,100.0,100.0,
100.0,100.0,100.0,100.0,80.0,80.0,80.0,100.0,100.0,25.0,
100.0,100.0,100.0,75.0,100.0,100.0,100.0,25.0,100.0,100.0,
Results calculated
0:4,0,
1:3,1,
2:7,2,
3:6,3,
4:0,4,
5:2,5,
6:1,6,
7:9,7,
8:5,8,
9:8,9,

Answer 1

这是任务问题.您可以将行视为"人员",将列视为"分配".您希望最小化(嗯,您希望最大化但想法仍然存在)总成本,每个人可以执行一项任务matrix[i][j] money.

在匈牙利算法是一个很好的解决方案,但它是相当复杂的.我认为强制它可以在15x15矩阵上正常工作.