【求助】在元素总和为1的k*k的浮点数矩阵中找到和最大的不同行不同列的元素排列
k为整数,取值是2<=k<=20,m是k*k的浮点数矩阵,m中所有元素的和等于1,找出m中和最大的不同行不同列的元素排列。
例如:k=3,m=[
0.20 0.19 0.01
0.19 0.04 0.18
0.01 0.01 0.17
]
正确结果:
1 2 0.19
2 1 0.19
3 3 0.17
从左往右的三列分别是行号、列号、矩阵中的元素。
这个问题的规模是k!,普通的暴力搜索时间复杂度是o(k!),
当k>=10时,暴力搜索就以及相当慢了。
求助大神给个效率高的算法(贪心算法就免了吧,这个我已经实现了),
如果最优解找不到极优解也是可以的,
然后不需要完整的代码,描述下算法思想就好了。