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

寻找一个对动态规划算法有研究的大佬,想付费请教个工作上遇到的复杂算法问题

  •  
  •   ceneri · 2022-10-25 14:18:59 +08:00 · 4395 次点击
    这是一个创建于 520 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大概是背包问题的衍生,背包问题是有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 c[i],价值是 w[i]。求解将哪些物品装入背包可使价值总和最大。

    我这边需求是有 N 件物品,每件物品对应不同的数量和大小,有 X 种类型的柜子,柜子可以多台组合,柜子里格口大小均可能不同,不同的柜子成本不同,计算能将所有物品装入柜子且机器成本最低的方案。

    因为是工作上遇到的需求还需要结合业务场景讲解,会付费给大佬,给出思路即可,不求代码实现,麻烦有兴趣的大佬加下我微信:Q2VuZXJpaQ==

    33 条回复    2022-10-27 21:22:36 +08:00
    dwlovelife
        1
    dwlovelife  
       2022-10-25 14:20:00 +08:00
    是妹子么
    nulIptr
        2
    nulIptr  
       2022-10-25 14:31:23 +08:00
    抛个砖,如果是工业或是商业解决方案的话可能不是一个真正纯动态规划问题
    古时候在老东家做简单的 aps ,就是有工单人员设备日历,自动排程的问题,看似是动态规划,但是限制条件太多了导致最后发现还是先找最大权重的条件暴力模拟简单。。。
    ceneri
        3
    ceneri  
    OP
       2022-10-25 14:35:47 +08:00
    @dwlovelife 是的,JAVA 后端
    zhaorunze
        4
    zhaorunze  
       2022-10-25 14:39:01 +08:00
    可以看看美团巨佬写的关于外卖配送的博客,不只是学习算法,还有别人整理的模型,对问题的定义都可以学习学习。

    工程级别的算法,不只是要定义问题抽象模型解决问题,还要有仿真模型哦,不然你都没法证明你的算法是有效率的。
    ceneri
        5
    ceneri  
    OP
       2022-10-25 14:40:29 +08:00
    @nulIptr 这点我也有感觉,这个需求也有一定的限制,我对算法的研究程度不深,所以想问下其他人能否用动态规划求解,如果没办法的话,用暴力求解那如何优化复杂度,这都是我想咨询的。
    msg7086
        6
    msg7086  
       2022-10-25 14:42:51 +08:00   ❤️ 2
    光听需求,可能不是动规。
    动规是要能做到局部最优解,然后往上挂状态转移方程。
    这里假如已经用 x 个柜子装了 y 件物品,再装入一个新物品的时候,前一个局部解可能就不是最优解了。

    比如 y 件物品正好塞满一个柜子,y+1 件商品变成一个柜子+一个小柜子,但是低成本方案可能是平均拆成两个中柜子。
    paopjian
        7
    paopjian  
       2022-10-25 14:56:53 +08:00
    试试用 utools?https://developers.google.com/optimization/bin/bin_packing 有现成的解决方案
    paopjian
        8
    paopjian  
       2022-10-25 14:57:43 +08:00
    @paopjian OR-Tools 说错了
    qwertyzzz
        9
    qwertyzzz  
       2022-10-25 15:06:38 +08:00
    还真有人在讨论算法 我先加微信再说 嘿嘿
    zhoudaiyu
        10
    zhoudaiyu  
       2022-10-25 15:12:26 +08:00
    YVAN7123
        11
    YVAN7123  
       2022-10-25 15:20:03 +08:00
    @dwlovelife 你问到重点了 ~ 钱不钱不重要
    dwlovelife
        12
    dwlovelife  
       2022-10-25 15:31:49 +08:00
    @YVAN7123 哈哈,帮兄弟们问的
    xuqd
        13
    xuqd  
       2022-10-25 15:32:52 +08:00
    OptaPlanner, 这个好像可以处理复杂规划
    dwlovelife
        14
    dwlovelife  
       2022-10-25 15:36:46 +08:00
    妹子给你推荐一个东西 叫规则引擎 这种业务代码 单纯的算法可以完成 但是代码耦合相当高 正常这种玩意如果是我做 我建议把规则放在存储层 然后指定规则模版 拿规则引擎去撞
    aeron
        15
    aeron  
       2022-10-25 15:49:41 +08:00
    去年做 APS 时研究过,最后扔给 ortools 算了
    optional
        16
    optional  
       2022-10-25 16:05:47 +08:00 via iPhone
    这是个整数优化问题,上 ortools ,复杂的话再来点启发式算法
    XSDo
        17
    XSDo  
       2022-10-25 16:23:38 +08:00
    动态规划的变种,如果看动态规划的算法是解决不了问题的,要做调整才行的
    zhaorunze
        18
    zhaorunze  
       2022-10-25 17:04:51 +08:00
    @zhoudaiyu 是的,我感觉写的很好
    MoYi123
        19
    MoYi123  
       2022-10-25 18:35:47 +08:00
    十有八九是个 np 问题, 建议凭经验直接搞个启发式得了.
    helloworld000
        20
    helloworld000  
       2022-10-25 18:50:52 +08:00
    好奇问一下这种 hash 微信号怎么恢复成真正的号码?
    renmu
        21
    renmu  
       2022-10-25 19:27:29 +08:00 via Android
    钱不钱不重要,我们可以线下仔细沟通业务场景和算法(狗头)
    bruce0
        22
    bruce0  
       2022-10-25 19:29:59 +08:00
    我原本还想加个 wx,可是我大概率也给不出好的解决方案, 还是别这么不要脸了😢
    SunsetShimmer
        23
    SunsetShimmer  
       2022-10-25 19:33:31 +08:00   ❤️ 1
    @helloworld000 这个应该是 Base64...

    (就算是 hash ,这么短的穷举应该也能解?)
    iOCZ
        24
    iOCZ  
       2022-10-25 20:21:51 +08:00
    偶然点开楼主的回帖,有个帖子让我的心沉了下去。。。
    nekoneko
        25
    nekoneko  
       2022-10-25 21:10:09 +08:00
    @SunsetShimmer #23 穷举的话 64 的 7 次方大概, 4 万亿次计算...
    berg223
        26
    berg223  
       2022-10-26 01:10:42 +08:00 via Android
    考虑现实意义,格口更大的柜子装 1 立方米的平均成本是否一定比格口小的成本低呢
    c0xt30a
        27
    c0xt30a  
       2022-10-26 01:43:04 +08:00
    有测试数据么?发一组上来尝试下。不习惯加陌生人微信。
    dayeye2006199
        28
    dayeye2006199  
       2022-10-26 02:13:21 +08:00
    我有个大规模整数优化的博士学位,可以接受咨询
    caixiangyu17
        29
    caixiangyu17  
       2022-10-26 07:57:06 +08:00
    @msg7086 感觉你最后的例子好像有一点问题,y+1 的解法不是吧 y 取出最优解加上一个。
    y+1 的解法是整合 y+1, (y-1)+2, (y-2)+3, (y-3)+4.....的所有解,取最优,所以你举着个例子正好是一个动态规划的方案。
    buliugu
        30
    buliugu  
       2022-10-26 08:59:59 +08:00
    optaplanner
    msg7086
        31
    msg7086  
       2022-10-26 13:55:26 +08:00 via Android
    @caixiangyu17 不对,你这里的 y-1 y-2 不是单个值,他们本身就是一个集合(取出任何一个或两个物品后的价值的最大值),所以会迅速放大计算量,失去动规的意义。
    ceneri
        32
    ceneri  
    OP
       2022-10-26 14:14:24 +08:00
    目前问题未解决,由于 deadline 逼近,希望有大佬能帮忙解决。目前我的困难是没办法根据需求抽象出计算模型,不求具体实现,提供抽象数学模型和可实现思路,预算 500 ,个人支付,有兴趣的老哥可以加下我。
    guyeu
        33
    guyeu  
       2022-10-27 21:22:36 +08:00
    看需求感觉不像是个动态规划问题,楼主有解法之后踢我一下,学习一个
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3933 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 10:25 · PVG 18:25 · LAX 03:25 · JFK 06:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.