V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
andersonGzy
V2EX  ›  程序员

求一个最大值解法

  •  
  •   andersonGzy · 2021-04-12 11:02:10 +08:00 · 2935 次点击
    这是一个创建于 1082 天前的主题,其中的信息可能已经有所发展或是发生改变。

    6e9a5c21688438e387b39fbec70a05e.png

    每个装备只能选一个属性,即一行只能有一个属性。

    每列可以有多个属性,也可以没有属性。

    每列上的数据先相加。

    每列相加之和各自加底数 1 之后再相乘。

    求最终最大值。 [穷举太慢,自己写的逻辑算出来 2.139 ,还不到最大]

    第 1 条附言  ·  2021-04-12 14:40:51 +08:00
    https://www.icloud.com/notes/0HSq5vdV2THOjss6yNj3qVJTQ
    这是我最开始的推算逻辑。
    27 条回复    2021-04-13 17:02:01 +08:00
    linvon
        1
    linvon  
       2021-04-12 11:15:08 +08:00
    这都 2021 年了,DNF 的计算器应该一大堆了吧,还用自己写?
    andersonGzy
        2
    andersonGzy  
    OP
       2021-04-12 11:18:32 +08:00
    @linvon 单纯的想知道,怎么解方便。。。
    no1xsyzy
        3
    no1xsyzy  
       2021-04-12 11:22:29 +08:00
    直觉上是个离散凸包优化,随机化算法会比较好

    用启发式爬坡算法
    先预设一个初始选择。
    第一层死循环;第二层循环每件装备,尝试重选;如果某轮循环中重新选取后不发生改变,则认为最优
    但可能实际上有局部最优,可以随机生成若干个初始选择,或者用把爬坡改退火

    ……

    但我想了想,6**8 也不过 167 万,太慢是不是干了什么诡异的或者多余的操作?
    kalluwa
        4
    kalluwa  
       2021-04-12 11:47:07 +08:00
    brute force 一下就算出来:2.34208
    ms 级别的计算量
    zyx199199
        5
    zyx199199  
       2021-04-12 11:48:10 +08:00   ❤️ 1
    整数线性规划求解。

    8 个装备定为 1-8 号。六种属性分别定为 a,b,c,d,e,f,。然后将他们组合,得到 a1, a2,...,b1, b2,...,f8,一共 48 个变量

    每个变量值只能取 0 或 1

    例如,用 a1 这个变量表示装备 1 是否选择 “力智” 这个属性。a1=1 表示装备 1 选择力智属性,a1=0 表示装备 1 不选择力智属性。

    最终求解的就是 ( a1*0.169 + a2*0.085+...+...+a8*0 + 1 )*...*( f1*0.186+...+f8*0+1 ) 的最大值。不过要满足一行最多只能选一个属性的条件,即

    a1+b1+c1+...+g1 <=1
    a2+b2+c2+...+g2 <= 1
    ...
    a8+b8+...+g8 <=1


    这种规模的数据,excel 就能解
    tabris17
        6
    tabris17  
       2021-04-12 11:52:23 +08:00
    线性规划问题,踩石法,我得把课本找出来看看了
    imn1
        7
    imn1  
       2021-04-12 13:18:34 +08:00
    8 行 6 列,一定有同一列重复的,重复的规则是什么?
    装备 7 为何不选 0.057 ,装备 8 为何不选 0.032 ?
    andersonGzy
        8
    andersonGzy  
    OP
       2021-04-12 13:33:13 +08:00
    @no1xsyzy 哈哈哈,我草率了,我最开始想着 2*8*6 就出结果了。
    andersonGzy
        9
    andersonGzy  
    OP
       2021-04-12 13:33:55 +08:00
    @kalluwa 直觉上暴力不是最慢的吗。大佬要不发下代码。
    andersonGzy
        10
    andersonGzy  
    OP
       2021-04-12 13:35:04 +08:00
    @zyx199199 主要是想用代码,活动活动我的小脑袋,就当它规模大吧。。。
    andersonGzy
        11
    andersonGzy  
    OP
       2021-04-12 13:36:58 +08:00
    @imn1 规则写了啊,至于为什么不选,图中下面的只是别人乱点的数据,是范例。
    imn1
        12
    imn1  
       2021-04-12 14:01:56 +08:00
    @andersonGzy #11
    装备 1 至 7 都选白字,装备 8 选“三攻”,那结果就是 2.169
    就是选每行的最大值,这种选法也是允许的?(不是最大,只是举例)
    我起初以为每列都至少需要一个
    andersonGzy
        13
    andersonGzy  
    OP
       2021-04-12 14:10:59 +08:00
    @imn1 允许的。你这么只有 1.032 * 1.815 = 1.87308,老小了。
    imn1
        14
    imn1  
       2021-04-12 14:19:13 +08:00
    @andersonGzy #13
    不对,是 2.x * 1.032 ,要加底数 1,除非你还有规则说明合计超过 1 时不加底数
    imn1
        15
    imn1  
       2021-04-12 14:21:21 +08:00
    @andersonGzy #13
    呃,好像是我摁错计算器了……尴尬
    xuegy
        16
    xuegy  
       2021-04-12 14:31:40 +08:00 via iPhone
    投机取巧的办法
    (1+a+b)=(1+a)*(1+b)-a*b,数都不大的所以先忽略 a*b
    所以全+1,直接算乘积最大,为求保险,可以取最大前 10 项,然后再从候选的里面算一遍真实的。
    andersonGzy
        17
    andersonGzy  
    OP
       2021-04-12 17:01:45 +08:00
    @xuegy 投不出来
    Marine5174
        18
    Marine5174  
       2021-04-12 17:14:16 +08:00
    将这个矩阵理解为一个(M,N)的完全二分图的边的权重,问题即为求该二分图的最大匹配.
    timsensor
        19
    timsensor  
       2021-04-12 19:30:54 +08:00
    excel 或者 wps 可以做规划求解
    leewangyang
        20
    leewangyang  
       2021-04-12 23:00:55 +08:00 via Android
    可以当作二部图带权匹配问题吧,如果是简单加法有 KN 算法。但是如果还要+1 算乘积,可能得改改。
    xml123
        21
    xml123  
       2021-04-13 00:18:38 +08:00
    怎么我算出来的最大只有 2.145
    选的分别是 2, 1, 4, 6, 5, 4, 4, 5
    proxychains
        22
    proxychains  
       2021-04-13 06:54:59 +08:00
    dnf 玩家...
    andersonGzy
        23
    andersonGzy  
    OP
       2021-04-13 09:11:32 +08:00
    @timsensor 朋友,几万件装备也用 Excel 吗 - -。
    aptx4689
        24
    aptx4689  
       2021-04-13 10:43:28 +08:00
    andersonGzy
        25
    andersonGzy  
    OP
       2021-04-13 10:53:24 +08:00
    @aptx4689 em...就是要改这个东西,它就是问题的起源。
    fcxxzux
        26
    fcxxzux  
       2021-04-13 14:57:48 +08:00
    就按照 zyx199199 写的思路,然后找个求解器来算最优解就行。
    比如,Google OR-Tools https://developers.google.com/optimization/cp/integer_opt_cp
    或者 Z3 https://github.com/Z3Prover/z3/blob/master/examples/python/tutorial/jupyter/guide.ipynb
    (声明:没用过 Z3,用过 Google OR-Tools 解 500*50 个 0/1 变量和一堆复杂条件结合的问题,开了 8 个 worker ~40 秒)
    andersonGzy
        27
    andersonGzy  
    OP
       2021-04-13 17:02:01 +08:00
    @fcxxzux 老哥这个我不会,求解器也没用过。
    看了一下自己试着写了写,稀碎。
    有空帮忙写个我这个情况的 demo 吗。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2688 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 15:13 · PVG 23:13 · LAX 08:13 · JFK 11:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.