请教一个矩阵算法问题# JobHunting - 待字闺中
h*t
1 楼
对于一个只有0和1的n by n的稀疏矩阵， 怎么找出相应的m by m的小矩阵，m
目标是使得找到的矩阵的1最多
最好时间复杂度低一些，谢谢
目标是使得找到的矩阵的1最多
最好时间复杂度低一些，谢谢
c*p
2 楼
这个难道不是选原矩阵才是最优解么。。。
【在 h***t 的大作中提到】
: 对于一个只有0和1的n by n的稀疏矩阵， 怎么找出相应的m by m的小矩阵，m
: 目标是使得找到的矩阵的1最多
: 最好时间复杂度低一些，谢谢
【在 h***t 的大作中提到】
: 对于一个只有0和1的n by n的稀疏矩阵， 怎么找出相应的m by m的小矩阵，m
: 目标是使得找到的矩阵的1最多
: 最好时间复杂度低一些，谢谢
h*t
3 楼
我表述有问题？ 其实就是想找出一个1的密度最高的m by m矩阵
【在 c****p 的大作中提到】
: 这个难道不是选原矩阵才是最优解么。。。
【在 c****p 的大作中提到】
: 这个难道不是选原矩阵才是最优解么。。。
c*p
4 楼
我知道你想要找啥样的，，，
但是原题表述是说要1最多的。。。
这个m by m矩阵的主对角线是不是还必须和原矩阵的主对角线重合才符合要求？
【在 h***t 的大作中提到】
: 我表述有问题？ 其实就是想找出一个1的密度最高的m by m矩阵
但是原题表述是说要1最多的。。。
这个m by m矩阵的主对角线是不是还必须和原矩阵的主对角线重合才符合要求？
【在 h***t 的大作中提到】
: 我表述有问题？ 其实就是想找出一个1的密度最高的m by m矩阵
c*t
5 楼
你的问题没有说明白。请给个例子来说明。
谢谢！
【在 h***t 的大作中提到】
: 我表述有问题？ 其实就是想找出一个1的密度最高的m by m矩阵
谢谢！
【在 h***t 的大作中提到】
: 我表述有问题？ 其实就是想找出一个1的密度最高的m by m矩阵
h*t
6 楼
不需要对角线重合啊
我现在想到的是先找到一个1最多的行， 然后根据这个行，利用类似树的结构把连接的
行放进来，继续做，但不知道有没有更好的办法
【在 c****p 的大作中提到】
: 我知道你想要找啥样的，，，
: 但是原题表述是说要1最多的。。。
: 这个m by m矩阵的主对角线是不是还必须和原矩阵的主对角线重合才符合要求？
我现在想到的是先找到一个1最多的行， 然后根据这个行，利用类似树的结构把连接的
行放进来，继续做，但不知道有没有更好的办法
【在 c****p 的大作中提到】
: 我知道你想要找啥样的，，，
: 但是原题表述是说要1最多的。。。
: 这个m by m矩阵的主对角线是不是还必须和原矩阵的主对角线重合才符合要求？
h*t
7 楼
比如我有一个4 x 4的矩阵，如下
1 0 1 0
1 0 0 0
1 1 1 1
0 0 1 0
现在要找一个2 x 2 的矩阵， 1 最多的
那就是原矩阵 第1，3行和第1，3列组成的2 x 2矩阵
选取的行的序号和列的序号一样了。
【在 c*********t 的大作中提到】
: 你的问题没有说明白。请给个例子来说明。
: 谢谢！
1 0 1 0
1 0 0 0
1 1 1 1
0 0 1 0
现在要找一个2 x 2 的矩阵， 1 最多的
那就是原矩阵 第1，3行和第1，3列组成的2 x 2矩阵
选取的行的序号和列的序号一样了。
【在 c*********t 的大作中提到】
: 你的问题没有说明白。请给个例子来说明。
: 谢谢！
c*p
8 楼
这样啊，那还是喽，最终选取的m x m子矩阵中，必然有m个元素是在原矩阵的主对角线
上。
【在 h***t 的大作中提到】
: 比如我有一个4 x 4的矩阵，如下
: 1 0 1 0
: 1 0 0 0
: 1 1 1 1
: 0 0 1 0
: 现在要找一个2 x 2 的矩阵， 1 最多的
: 那就是原矩阵 第1，3行和第1，3列组成的2 x 2矩阵
: 选取的行的序号和列的序号一样了。
上。
【在 h***t 的大作中提到】
: 比如我有一个4 x 4的矩阵，如下
: 1 0 1 0
: 1 0 0 0
: 1 1 1 1
: 0 0 1 0
: 现在要找一个2 x 2 的矩阵， 1 最多的
: 那就是原矩阵 第1，3行和第1，3列组成的2 x 2矩阵
: 选取的行的序号和列的序号一样了。
相关阅读
急问一下关于h1b transferMS的MDOP组，有人熟悉吗？急问：H1B没赶上，能否OPT转CPT？另问达拉斯地区学校好朋友刚刚面完G 求bless,thanks!update:被拒求分析大家找工作时，每天投几个简历？请教：大学里的博士后，H1B签证，找到公司的工作 (转载)开始时间最悲摧的事情Greenplum这个公司怎么样？非编程题H1B没赶上，有人了解L1吗？请教：子公司需要向总公司要求approval然后给offer吗？h1b一点问题，能不能凭旅游签证提前入境很诡异的面试redbus2us上的估计已经错了一半了afmgl的非fresh面试 coding比重大吗？谁能给几个Research Lab的工资行情（CS）简历问题cisco店面加悲剧jobvite这单位咋样啊， 有谁面过没啊？