请教大家一个算法问题，如何计算 N*N 维矩阵中的 N 数之积，值最大，每行每列仅选一个

维矩阵

请教

算法

计算

20 replies

1

ZRS

Oct 2, 2019

1

如果可以保证矩阵元素都是大于 1 的，对每个元素取对数，用匈牙利算法求解。

2

Caturra

Oct 2, 2019

2

只考虑正整数的话按行列拆分成二分图，边对应数的权值，然后跑 MCMF·改，把费用累加改成累乘（我瞎说的

3

oIMOo

Oct 2, 2019

为什么楼上都看懂问题了……

比如 3*3 的矩阵：
1 2 3
7 4 2
9 6 3

N 数之积 -> 3 个数字的乘积

值最大，每行只选一个 -> 选每行最大的，分别是 3，7，9，然后乘起来不就好了么？

4

oIMOo

Oct 2, 2019

@oIMOo 不对不对
我没看到每列…… 丢脸……
请无视我……

5

aneureka

Oct 2, 2019 via Android

1

有丶八皇后简略版的意思？？但我不知道直接回溯是不是复杂度会太高，如果楼主没有解决过这类问题建议看看八皇后。

6

midasplus

Oct 2, 2019 via Android

好像可以上 KM……（？）

7

ilotuo

Oct 2, 2019

我的思路:
先用 dfs 生成 range(1, n) 序列的排列组合, 共 n!种组合. 每个组合都有对应的乘积, 取组合中最大的一个即可.
如 3 楼的例子, 有组合 1,2,3 ; 1,3,2; 2,1,3; 2,3,1, ....
对应的乘积: 1*4*3; 1*2*6; 2*7*3; 2*2*9; ....
找其中最大的一个即可;

8

ilotuo

Oct 2, 2019

组合--> 排列
说错了.

9

threebr

Oct 2, 2019 via Android

用递归做搜索，思路上跟八皇后问题比较像

10

jtnwm

Oct 2, 2019

看不太明白，这个答案是唯一的吗？

11

threebr

Oct 2, 2019 via Android

@threebr 好吧，我想不出递归搜索的方法

12

zzyyzz1992

Oct 2, 2019

动态规划老哥

13

billwsy

Oct 2, 2019 via iPhone

@111qqz 我也觉得是 KM…但是不会写所以我选择费用流

14

optional

Oct 2, 2019 via Android

乘积最大子序列 * N

15

optional

Oct 2, 2019 via Android

不对不对列不能复选

16

dingyaguang117

Oct 3, 2019

@zzyyzz1992
动态规划 O(N*2^N)) 感觉还是高

17

aguesuka

Oct 3, 2019 via Android

任意两行交换不影响结果，我觉得线性代数里应该有好办法

18

optional

Oct 5, 2019

1

@SheerCold
回来看到 @aguesuka 说的『交换行列不影响结果』大受启发，那么最终结果肯定可以交换行列成一个斜线。
先把求积变成求和，简化思考：只要在边缘找（ n 行 n 列）一个合适的数字（对于求和就是数字最大），把它所在的行或者列交换到 0 行 0 列，然后递归(n-1)这个矩阵，就能找到这 n 个数字。
对于求积，无非稍微复杂点是做个 dp 而已，但是复杂度是一样的。

19

optional

Oct 5, 2019

复杂度应该是 N^2

20

optional

Oct 7, 2019 via iPhone

不对