| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4649 人关注过本帖
标题:【求助】在元素总和为1的k*k的浮点数矩阵中找到和最大的不同行不同列的元素 ...
只看楼主 加入收藏
客气猫
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2018-12-24
结帖率:0
收藏
已结贴  问题点数:20 回复次数:2 
【求助】在元素总和为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时,暴力搜索就以及相当慢了。

求助大神给个效率高的算法(贪心算法就免了吧,这个我已经实现了),
如果最优解找不到极优解也是可以的,
然后不需要完整的代码,描述下算法思想就好了。
搜索更多相关主题的帖子: 元素 浮点数 矩阵 不同 排列 
2018-12-24 17:07
MeandC
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:8
帖 子:245
专家分:792
注 册:2018-7-14
收藏
得分:20 
没有想到更高效的,20的嵌套循环问题不大,很快就会有结果.

C果然是有点难啊!
2018-12-24 20:11
matianwu
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2020-1-3
收藏
得分:0 
指派问题,匈牙利算法。
2020-04-21 09:59
快速回复:【求助】在元素总和为1的k*k的浮点数矩阵中找到和最大的不同行不同列的 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020302 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved