rt,不知道应该怎么实现了
1
ZRS 2019-10-02 15:35:06 +08:00 1
如果可以保证矩阵元素都是大于 1 的,对每个元素取对数,用匈牙利算法求解。
|
2
Caturra 2019-10-02 15:40:34 +08:00 2
只考虑正整数的话按行列拆分成二分图,边对应数的权值,然后跑 MCMF·改,把费用累加改成累乘(我瞎说的
|
3
oIMOo 2019-10-02 15:47:44 +08:00
为什么楼上都看懂问题了……
比如 3*3 的矩阵: 1 2 3 7 4 2 9 6 3 N 数之积 -> 3 个数字的乘积 值最大,每行只选一个 -> 选每行最大的,分别是 3,7,9,然后乘起来不就好了么? |
5
aneureka 2019-10-02 16:28:27 +08:00 via Android 1
有丶八皇后简略版的意思?? 但我不知道直接回溯是不是复杂度会太高,如果楼主没有解决过这类问题建议看看八皇后。
|
6
111qqz 2019-10-02 16:36:58 +08:00 via Android
好像可以上 KM……(?)
|
7
ilotuo 2019-10-02 17:28:36 +08:00
我的思路:
先用 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 2019-10-02 17:32:20 +08:00
组合--> 排列
说错了. |
9
threebr 2019-10-02 17:42:33 +08:00 via Android
用递归做搜索,思路上跟八皇后问题比较像
|
10
jtnwm 2019-10-02 18:21:17 +08:00
看不太明白,这个答案是唯一的吗?
|
12
zzyyzz1992 2019-10-02 22:20:08 +08:00
动态规划老哥
|
14
optional 2019-10-02 23:37:13 +08:00 via Android
乘积最大子序列 * N
|
15
optional 2019-10-02 23:38:01 +08:00 via Android
不对 不对 列不能复选
|
16
dingyaguang117 2019-10-03 09:26:43 +08:00
@zzyyzz1992
动态规划 O(N*2^N)) 感觉还是高 |
17
aguesuka 2019-10-03 10:58:33 +08:00 via Android
任意两行交换不影响结果,我觉得线性代数里应该有好办法
|
18
optional 2019-10-05 08:51:14 +08:00 1
|
19
optional 2019-10-05 08:59:13 +08:00
复杂度应该是 N^2
|
20
optional 2019-10-07 20:52:12 +08:00 via iPhone
不对
|