m****s
发帖数: 1481 | 1 一个 MxN 的矩阵，里面的元素都是随机实数。
现在要选择其中的 m行，n列， 1<=m<=M，1<=n<=N，使得这些被选择的行列的交叉处的
数字之和是所有可能的选择方式中最大的。
问如何选择，或者说什么算法。exhaustive search不算。
这个问题我一筹莫展，最终放弃，然后问面试官解答是啥，他说他也不知道，就是随便
想到一个问题看看我有什么思路。。。 |
f*****e
发帖数: 2992 | 2 xi yi
sum(wij*xi*yi)
x^TWy最大，
如果是对称的就好办了。就是最大割。有非常好的近似算法。
【在 m****s 的大作中提到】
: 一个 MxN 的矩阵，里面的元素都是随机实数。
: 现在要选择其中的 m行，n列， 1<=m<=M，1<=n<=N，使得这些被选择的行列的交叉处的
: 数字之和是所有可能的选择方式中最大的。
: 问如何选择，或者说什么算法。exhaustive search不算。
: 这个问题我一筹莫展，最终放弃，然后问面试官解答是啥，他说他也不知道，就是随便
: 想到一个问题看看我有什么思路。。。
|
m****s
发帖数: 1481 | 3 能展开说说么
另外如果是完全没规律的随机分布，有什么快速算法么 |
q*****l
发帖数: 124 | 4 combinatorial optimization? |
l******n
发帖数: 9344 | 5 这个都不是方阵 ...
可以随机产生m by n矩阵，然后比较和，大就keep,否则就discard,循环一定次数，最
后结果作为近似
【在 f*****e 的大作中提到】
: xi yi
: sum(wij*xi*yi)
: x^TWy最大，
: 如果是对称的就好办了。就是最大割。有非常好的近似算法。
|
A**u
发帖数: 2458 | 6 quant面试真好
随便问啊
不会做，有个类似的题目，做过，看有帮助没
选m,n列，有mxn个交点
组成mxn的子矩阵，不一定连续的
有一个道题目，找最大和的子矩阵, DP 你搜搜
【在 m****s 的大作中提到】
: 一个 MxN 的矩阵，里面的元素都是随机实数。
: 现在要选择其中的 m行，n列， 1<=m<=M，1<=n<=N，使得这些被选择的行列的交叉处的
: 数字之和是所有可能的选择方式中最大的。
: 问如何选择，或者说什么算法。exhaustive search不算。
: 这个问题我一筹莫展，最终放弃，然后问面试官解答是啥，他说他也不知道，就是随便
: 想到一个问题看看我有什么思路。。。
|
k****e
发帖数: 647 | 7 YES, DP. Find a clip on youtube. may check it later
【在 A**u 的大作中提到】
: quant面试真好
: 随便问啊
: 不会做，有个类似的题目，做过，看有帮助没
: 选m,n列，有mxn个交点
: 组成mxn的子矩阵，不一定连续的
: 有一个道题目，找最大和的子矩阵, DP 你搜搜
|
k****e
发帖数: 647 | 8 A more interesting problem can be
if the matrix is sparse, lots of 0, and the matrix is in the form of sparse
representation (3 long columns), how to find an efficient solution.
【在 A**u 的大作中提到】
: quant面试真好
: 随便问啊
: 不会做，有个类似的题目，做过，看有帮助没
: 选m,n列，有mxn个交点
: 组成mxn的子矩阵，不一定连续的
: 有一个道题目，找最大和的子矩阵, DP 你搜搜
|
r*********n
发帖数: 4553 | 9 再下去就发展成学术问题了，呵呵....
sparse
【在 k****e 的大作中提到】
: A more interesting problem can be
: if the matrix is sparse, lots of 0, and the matrix is in the form of sparse
: representation (3 long columns), how to find an efficient solution.
|
