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

[cyrbuzz]

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

场景是这样的：

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

[czfy]

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

[cyrbuzz]

@czfy 全流程自动化的。

[MoYi123]

感觉是个 np 问题.

[misdake]

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

[chenxytw]

Bin packing problem.

[index90]

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

[timethinker]

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

[libook]

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

[yehoshua]

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

[sudoy]

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

[cyrbuzz]

@misdake
@index90

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

[cyrbuzz]

@chenxytw

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

[cyrbuzz]

@qwe520liao
@sudoy

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

[xupefei]

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

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

[cyrbuzz]

@libook

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

[cyrbuzz]

@yehoshua

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

[cyrbuzz]

@xupefei

好的大佬！我去查查看。

[yehoshua]

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

[ncepuzs]

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

[flyingghost]

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

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

[fcxxzux]

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

[xuanbg]

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

[cyrbuzz]

@yehoshua
@flyingghost

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

[cyrbuzz]

@fcxxzux

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

[cyrbuzz]

@xuanbg

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

[joApioVVx4M4X6Rf]

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

[ccraohng]

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

[wangtian2020]

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

[gablic]

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