V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
SheerCold
V2EX  ›  问与答

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

  •  
  •   SheerCold · 2019-10-02 15:09:25 +08:00 · 2672 次点击
    这是一个创建于 1864 天前的主题,其中的信息可能已经有所发展或是发生改变。

    rt,不知道应该怎么实现了

    20 条回复    2019-10-07 20:52:12 +08:00
    ZRS
        1
    ZRS  
       2019-10-02 15:35:06 +08:00   ❤️ 1
    如果可以保证矩阵元素都是大于 1 的,对每个元素取对数,用匈牙利算法求解。
    Caturra
        2
    Caturra  
       2019-10-02 15:40:34 +08:00   ❤️ 2
    只考虑正整数的话按行列拆分成二分图,边对应数的权值,然后跑 MCMF·改,把费用累加改成累乘(我瞎说的
    oIMOo
        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,然后乘起来不就好了么?
    oIMOo
        4
    oIMOo  
       2019-10-02 15:48:31 +08:00
    @oIMOo 不对不对
    我没看到每列…… 丢脸……
    请无视我……
    aneureka
        5
    aneureka  
       2019-10-02 16:28:27 +08:00 via Android   ❤️ 1
    有丶八皇后简略版的意思?? 但我不知道直接回溯是不是复杂度会太高,如果楼主没有解决过这类问题建议看看八皇后。
    111qqz
        6
    111qqz  
       2019-10-02 16:36:58 +08:00 via Android
    好像可以上 KM……(?)
    ilotuo
        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; ....
    找其中最大的一个即可;
    ilotuo
        8
    ilotuo  
       2019-10-02 17:32:20 +08:00
    组合--> 排列
    说错了.
    threebr
        9
    threebr  
       2019-10-02 17:42:33 +08:00 via Android
    用递归做搜索,思路上跟八皇后问题比较像
    jtnwm
        10
    jtnwm  
       2019-10-02 18:21:17 +08:00
    看不太明白,这个答案是唯一的吗?
    threebr
        11
    threebr  
       2019-10-02 18:24:54 +08:00 via Android
    @threebr 好吧,我想不出递归搜索的方法
    zzyyzz1992
        12
    zzyyzz1992  
       2019-10-02 22:20:08 +08:00
    动态规划老哥
    billwsy
        13
    billwsy  
       2019-10-02 23:12:46 +08:00 via iPhone
    @111qqz 我也觉得是 KM…但是不会写所以我选择费用流
    optional
        14
    optional  
       2019-10-02 23:37:13 +08:00 via Android
    乘积最大子序列 * N
    optional
        15
    optional  
       2019-10-02 23:38:01 +08:00 via Android
    不对 不对 列不能复选
    dingyaguang117
        16
    dingyaguang117  
       2019-10-03 09:26:43 +08:00
    @zzyyzz1992
    动态规划 O(N*2^N)) 感觉还是高
    aguesuka
        17
    aguesuka  
       2019-10-03 10:58:33 +08:00 via Android
    任意两行交换不影响结果,我觉得线性代数里应该有好办法
    optional
        18
    optional  
       2019-10-05 08:51:14 +08:00   ❤️ 1
    @SheerCold
    回来看到 @aguesuka 说的『交换行列不影响结果』大受启发,那么最终结果肯定可以交换行列成一个斜线。
    先把求积变成求和,简化思考:只要在边缘找( n 行 n 列)一个合适的数字(对于求和就是数字最大),把它所在的行或者列交换到 0 行 0 列,然后递归(n-1)这个矩阵,就能找到这 n 个数字。
    对于求积,无非稍微复杂点是做个 dp 而已,但是复杂度是一样的。
    optional
        19
    optional  
       2019-10-05 08:59:13 +08:00
    复杂度应该是 N^2
    optional
        20
    optional  
       2019-10-07 20:52:12 +08:00 via iPhone
    不对
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1154 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 18:39 · PVG 02:39 · LAX 10:39 · JFK 13:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.