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

老哥们,一个算法求个思路

  •  
  •   cyrbuzz ·
    HuberTRoy · 151 天前 · 2161 次点击
    这是一个创建于 151 天前的主题,其中的信息可能已经有所发展或是发生改变。

    老哥们求教,给难住了= =。

    场景是这样的:

    有很多 PDF ,准备发给不同的邮箱,但因为邮箱附件的大小限制,每一封邮件只能发送 50MB 的附件,所以需要将待发送的 PDF 进行合理的切分,用尽可能少的发件数量完成发送,每个 PDF 都不会超过 50MB 。

    目前的策略是排序后从大到小做的贪心切分,实际多发一封也没啥问题,就是没解出来有点堵得慌...尝试了 DP 好像又不完全是 DP 也可能姿势不对 /(ㄒoㄒ)/~~。

    一个例子,下面表示文件大小:

    [1,2,3,5,8,9,12] max 为 20 时期望的切分出来的结果是:

    [[1,2,3,5,9], [8, 12]] 或者 [[1,2,8,9],[3,5,12]],符合条件就可以= =。

    29 条回复    2021-12-29 16:15:58 +08:00
    czfy
        1
    czfy  
       151 天前
    这个 “有很多 PDF ,准备发给不同的邮箱” 一定要批量、自动化实现?
    还是实际上是人工、手动做的?
    cyrbuzz
        2
    cyrbuzz  
    OP
       151 天前
    @czfy 全流程自动化的。
    MoYi123
        3
    MoYi123  
       151 天前   ❤️ 1
    感觉是个 np 问题.
    misdake
        4
    misdake  
       151 天前
    算是一种背包问题吧,多个背包,要看到几个背包的时候能全部塞满
    chenxytw
        5
    chenxytw  
       151 天前   ❤️ 2
    Bin packing problem.
    index90
        6
    index90  
       151 天前
    每次做背包,做完一次背包,把已选择的文件剔除掉,做第二次背包,做完为止。
    qwe520liao
        7
    qwe520liao  
       151 天前
    有没有可能发一个网盘地址呢? [狗头]
    libook
        8
    libook  
       151 天前   ❤️ 7
    好说,所有 PDF 放到一个压缩包里,分卷,每个卷 50M (或者少一点点)。
    yehoshua
        9
    yehoshua  
       151 天前 via Android
    既然 pdf 能切割,那就直接切割成大小 50 的文件发送就可以了吧,不应该是背包算法。把每一个 50 塞满就行了。
    sudoy
        10
    sudoy  
       151 天前 via iPhone
    你这个场景是比喻还是真实的,如果是真实的,那么为何不上传到云盘然后邮件贴个网盘下载链接呢?
    cyrbuzz
        11
    cyrbuzz  
    OP
       151 天前
    @misdake
    @index90

    用这种思路,好像有点暴力= =...
    cyrbuzz
        12
    cyrbuzz  
    OP
       151 天前
    @chenxytw

    我去了解一下,谢谢老哥~。
    cyrbuzz
        13
    cyrbuzz  
    OP
       151 天前
    @qwe520liao
    @sudoy

    场景还是真实的,发邮件是必须的,网盘方案给否了[手动狗头]。
    xupefei
        14
    xupefei  
       151 天前   ❤️ 2
    PDF 不能切割的话就是 bin packing ,是一个 strong NP-hard 问题。一般情况下 best-fit 算法就够用了。

    PDF 能切割的话这个问题就变成了 fractional knapsack (非 NP-hard ),最优解是把 PDF 从大到小排序之后一个一个放,放不下的话就切开把当前背包塞满,剩余的放到一个新背包里。
    cyrbuzz
        15
    cyrbuzz  
    OP
       151 天前
    @libook

    妙啊老哥,加入保底方案了,想先实现试试。
    cyrbuzz
        16
    cyrbuzz  
    OP
       151 天前
    @yehoshua

    PDF 不可在分割,只能尽可能往里面塞。
    cyrbuzz
        17
    cyrbuzz  
    OP
       151 天前
    @xupefei

    好的大佬!我去查查看。
    yehoshua
        18
    yehoshua  
       151 天前 via Android
    @cyrbuzz 你说切分我以为是切分 pdf 的意思,不能分割确实是背包算法范畴。但我觉得分卷压缩文件是最好的方法。
    另外也可以用支持大附件的邮箱。
    ncepuzs
        19
    ncepuzs  
       151 天前
    这业务场景不是很能看懂,为啥非得以邮件附件的形式发送,上传到云存储然后提供下载链接不是更好吗?
    另外,还有一个问题,不同邮件服务提供商对于接收的邮件附件大小是否有限制,以及限制是多少?
    flyingghost
        20
    flyingghost  
       151 天前   ❤️ 3
    从邮件自身逻辑表达的完整性来讲,一封邮件讲一件事情,因体积关系被迫分拆,那就不应该使用各邮件分别带一部分 pdf 这种缺乏强关联的形式。这种思路是在鼓励漏掉文件。

    一定得强调是一个完整逻辑体,邮件标题 [1/3] 、 [2/3] 、 [3/3] 表达关联性,附件使用压缩分卷强迫关联性和完整性。
    fcxxzux
        21
    fcxxzux  
       151 天前   ❤️ 2
    如果对于最优解有执着的追求,pdf 数量也就几百个,
    可以试试规划求解器,比如 Google OR-Tools 有现成代码 https://developers.google.com/optimization/bin/bin_packing
    xuanbg
        22
    xuanbg  
       151 天前
    貌似很复杂,但实际上不就是按发送列表里面的最小附件容量切分文件吗?无非就是不同列表最小值不同罢了。如果是多个文件组合发给多个列表,那么针对不同列表,把多个文件分别打对应列表的最小值分包压缩就是了。
    cyrbuzz
        23
    cyrbuzz  
    OP
       150 天前
    @yehoshua
    @flyingghost

    分卷压缩之前确实没想到,已加入保底方案中,标题这个看到回复立马就实现了,谢谢!
    cyrbuzz
        24
    cyrbuzz  
    OP
       150 天前
    @fcxxzux

    强的老哥,这下可以跑测试用例验证了。
    cyrbuzz
        25
    cyrbuzz  
    OP
       150 天前
    @xuanbg

    还是有点不同的,已生成的 PDF 无法继续分割和融合,不能改变原 PDF 只能挑选组合他们。
    v2exblog
        26
    v2exblog  
       150 天前
    要发送的 PDF 打个压缩包,把大于 50M 的压缩包分割
    ccraohng
        27
    ccraohng  
       150 天前
    有些邮箱网易还是 qq 是 10mb 限制。
    对文件链接没有做安全限制,可以采用文件链接来下载
    wangtian2020
        28
    wangtian2020  
       150 天前
    如果是算法题我直接 DFS 梭了
    如果是实际应用我直接把所有文件 50MB 分卷压缩
    gablic
        29
    gablic  
       150 天前
    跑个题,能不能放云端邮件发链接
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1580 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:44 · PVG 01:44 · LAX 10:44 · JFK 13:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.