求问面试中遇到的疑似np-hard问题
有一个p行q列的矩阵,其中q>p,矩阵元素是数字,现在需要从每一行中各找出列索引不同的1个元素,使这p个元素之和最小。
换句话说,从p×q的矩阵里找出和最小的p个元素,其中这些元素各自的行和列都不相同。
换句话说,从p×q的矩阵里找出和最小的p个元素,其中这些元素各自的行和列都不相同。
全部评论
应该是二分图的最小权匹配,用费用流或者KM算法可以解,应该不是np-hard
相关推荐
点赞 评论 收藏
分享
05-07 14:11
大连工业大学 Java 
点赞 评论 收藏
分享