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

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 1597 days ago, the information mentioned may be changed or developed.

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

场景是这样的：

有很多 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]]，符合条件就可以= =。

PDF

切分

发送

哥们

29 replies • 2021-12-29 16:15:58 +08:00

jr55475f112iz2tu

Dec 28, 2021

这个 “有很多 PDF ，准备发给不同的邮箱” 一定要批量、自动化实现？
还是实际上是人工、手动做的？

cyrbuzz

Dec 28, 2021

@czfy 全流程自动化的。

MoYi123

Dec 28, 2021

感觉是个 np 问题.

misdake

Dec 28, 2021

算是一种背包问题吧，多个背包，要看到几个背包的时候能全部塞满

chenxytw

Dec 28, 2021

Bin packing problem.

index90

Dec 28, 2021

每次做背包，做完一次背包，把已选择的文件剔除掉，做第二次背包，做完为止。

timethinker

Dec 28, 2021

有没有可能发一个网盘地址呢？ [狗头]

libook

Dec 28, 2021

好说，所有 PDF 放到一个压缩包里，分卷，每个卷 50M （或者少一点点）。

thyyn

Dec 28, 2021 via Android

既然 pdf 能切割，那就直接切割成大小 50 的文件发送就可以了吧，不应该是背包算法。把每一个 50 塞满就行了。

sudoy

Dec 28, 2021 via iPhone

你这个场景是比喻还是真实的，如果是真实的，那么为何不上传到云盘然后邮件贴个网盘下载链接呢？

cyrbuzz

Dec 28, 2021

@misdake
@index90

用这种思路，好像有点暴力= =...

cyrbuzz

Dec 28, 2021

@chenxytw

我去了解一下，谢谢老哥~。

cyrbuzz

Dec 28, 2021

@qwe520liao
@sudoy

场景还是真实的，发邮件是必须的，网盘方案给否了[手动狗头]。

xupefei

Dec 28, 2021

PDF 不能切割的话就是 bin packing ，是一个 strong NP-hard 问题。一般情况下 best-fit 算法就够用了。

PDF 能切割的话这个问题就变成了 fractional knapsack （非 NP-hard ），最优解是把 PDF 从大到小排序之后一个一个放，放不下的话就切开把当前背包塞满，剩余的放到一个新背包里。

cyrbuzz

Dec 28, 2021

@libook

妙啊老哥，加入保底方案了，想先实现试试。

cyrbuzz

Dec 28, 2021

@yehoshua

PDF 不可在分割，只能尽可能往里面塞。

cyrbuzz

Dec 28, 2021

@xupefei

好的大佬！我去查查看。

thyyn

Dec 28, 2021 via Android

@cyrbuzz 你说切分我以为是切分 pdf 的意思，不能分割确实是背包算法范畴。但我觉得分卷压缩文件是最好的方法。
另外也可以用支持大附件的邮箱。

ncepuzs

Dec 28, 2021

这业务场景不是很能看懂，为啥非得以邮件附件的形式发送，上传到云存储然后提供下载链接不是更好吗？
另外，还有一个问题，不同邮件服务提供商对于接收的邮件附件大小是否有限制，以及限制是多少？

flyingghost

Dec 28, 2021

从邮件自身逻辑表达的完整性来讲，一封邮件讲一件事情，因体积关系被迫分拆，那就不应该使用各邮件分别带一部分 pdf 这种缺乏强关联的形式。这种思路是在鼓励漏掉文件。

一定得强调是一个完整逻辑体，邮件标题 [1/3] 、 [2/3] 、 [3/3] 表达关联性，附件使用压缩分卷强迫关联性和完整性。

fcxxzux

Dec 28, 2021

如果对于最优解有执着的追求，pdf 数量也就几百个，
可以试试规划求解器，比如 Google OR-Tools 有现成代码 https://developers.google.com/optimization/bin/bin_packing

xuanbg

Dec 28, 2021

貌似很复杂，但实际上不就是按发送列表里面的最小附件容量切分文件吗？无非就是不同列表最小值不同罢了。如果是多个文件组合发给多个列表，那么针对不同列表，把多个文件分别打对应列表的最小值分包压缩就是了。

cyrbuzz

Dec 29, 2021

@yehoshua
@flyingghost

分卷压缩之前确实没想到，已加入保底方案中，标题这个看到回复立马就实现了，谢谢！

cyrbuzz

Dec 29, 2021

@fcxxzux

强的老哥，这下可以跑测试用例验证了。

cyrbuzz

Dec 29, 2021

@xuanbg

还是有点不同的，已生成的 PDF 无法继续分割和融合，不能改变原 PDF 只能挑选组合他们。

joApioVVx4M4X6Rf

Dec 29, 2021

要发送的 PDF 打个压缩包，把大于 50M 的压缩包分割

ccraohng

Dec 29, 2021

有些邮箱网易还是 qq 是 10mb 限制。
对文件链接没有做安全限制，可以采用文件链接来下载

wangtian2020

Dec 29, 2021

如果是算法题我直接 DFS 梭了
如果是实际应用我直接把所有文件 50MB 分卷压缩

gablic

Dec 29, 2021

跑个题，能不能放云端邮件发链接