请教大家几个算法的小问题，急

1.一个N*N矩阵，每行每列一次只能取一个数，请问怎样取才能使取出的N个数和最小
2.一个N*N的bool矩阵，从中任取m个点，我想用这m个坐标做一个hash函数，
  请问用什么算法比较好？
这些是数据结构的问题吧，我不想找了，请大家多多帮忙，急用，最好有现成的
程序，分不够可以再加。

18 个解决方案

#1

1、应该是一个对角线吧。

#2

第一个问题记得是要用到二部图的匹配，有个匈牙利算法
第二个问题没看懂

#3

就是对m个坐标的hash函数，用什么算法才好？

#4

第二题:开一个N*N的向量组来做字典,对于选取的坐标直接按相同的下标在字典里映射就可以了.
第一题没看懂(每行每列一次只能取一个数?)

#5

“对角线”，很明显错。可以用到二部图的完美匹配吗？我没想到，原闻其详。
 这个问题很明显是个搜索问题，用DFS或BFS都行，当然也可加入启发式信息。

#6

第一题用动态规划，有最优子结构：
设矩阵m[N][N],最优解为min,包含元素m[i][j]，则(min-m[i][j])为去掉i行j列所剩矩阵的最优解。
程序就不写了，这明显是一个np难问题。

第二题对hash没研究，不过有印象说hash函数要求散列度高，计算要快（因为涉及多次存取计算），因此想象中只要按这两个原则来构造哈希函数，应该不成问题。

#7

我是这么想的（还不知是从哪儿看来的:)）：
把行号1..n和列号1..n看做是2n个顶点，则构成一个二部图，其边与矩阵元素一一对应，则此问题不就转化为一个最小匹配的问题了么，然后预先用一大数减去矩阵每个元素，问题就变成最大匹配了

#8

还请大家写详细些
最好有程序说明

#9

第二个问题象是用在第一个问题上的？

#10

http://it.swjtu.edu.cn:8080/courseware/yuncou/text/6/6-5.htm

#11

嗯，这个匈牙利法不错。

匈牙利人看来挺聪明。

#12

第一个问题在图论上看了，谢谢大家
第二个问题还是没找到又快又冲突小的算法

#13

还是不懂
你的hash函数到底是从哪儿到哪儿的映射阿，说详细些

#14

就是坐标，如(1,2)(2,3),(4,4)...一共5个坐标点，矩阵为20*20
我想将这5个坐标映射到一个hash表中，以便要使用时能快速找到，因为
可能很多5个点的组合，用哈希表可能快些

#15

你是想通过一个函数，将一个矩阵映射到5个坐标？还是别的什么？
说一下你的hash函数的定义域和值域

#16

我是想将5个坐标映射到hash表中
hash表可能有100000项大小
每一项存储这5个坐标，用一个hash函数来快速定位它

#17

哦，那我觉得好像没什么希望了
你的问题相当于找一个方法快速定位出与C(20*20,5)中的一个组合
有困难。。。
你想做什么啊

#18

不好办了，还是要谢谢你了
散分了