这是一个创建于 1382 天前的主题，其中的信息可能已经有所发展或是发生改变。
老哥们求教，给难住了= =。
场景是这样的：
有很多 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]]，符合条件就可以= =。
 | 1 jr55475f112iz2tu 2021-12-28 17:47:58 +08:00 这个 “有很多 PDF ，准备发给不同的邮箱” 一定要批量、自动化实现？ 还是实际上是人工、手动做的？ |
 | 3 MoYi123 2021-12-28 17:51:32 +08:00  1 感觉是个 np 问题. |
 | 4 misdake 2021-12-28 17:52:47 +08:00 算是一种背包问题吧，多个背包，要看到几个背包的时候能全部塞满 |
 | 5 chenxytw 2021-12-28 17:55:02 +08:00 2 Bin packing problem. |
 | 6 index90 2021-12-28 18:00:27 +08:00 每次做背包，做完一次背包，把已选择的文件剔除掉，做第二次背包，做完为止。 |
 | 7 timethinker 2021-12-28 18:01:32 +08:00 有没有可能发一个网盘地址呢？ [狗头] |
 | 8 libook 2021-12-28 18:03:47 +08:00 7 好说，所有 PDF 放到一个压缩包里，分卷，每个卷 50M （或者少一点点）。 |
 | 9 yehoshua 2021-12-28 18:05:22 +08:00 via Android 既然 pdf 能切割，那就直接切割成大小 50 的文件发送就可以了吧，不应该是背包算法。把每一个 50 塞满就行了。 |
 | 10 sudoy 2021-12-28 18:06:01 +08:00 via iPhone 你这个场景是比喻还是真实的，如果是真实的，那么为何不上传到云盘然后邮件贴个网盘下载链接呢？ |
 | 13 cyrbuzz OP |
 | 14 xupefei 2021-12-28 18:16:08 +08:00 2 PDF 不能切割的话就是 bin packing ，是一个 strong NP-hard 问题。一般情况下 best-fit 算法就够用了。 PDF 能切割的话这个问题就变成了 fractional knapsack （非 NP-hard ），最优解是把 PDF 从大到小排序之后一个一个放，放不下的话就切开把当前背包塞满，剩余的放到一个新背包里。 |
| 18 yehoshua 2021-12-28 18:36:11 +08:00 via Android @cyrbuzz 你说切分我以为是切分 pdf 的意思，不能分割确实是背包算法范畴。但我觉得分卷压缩文件是最好的方法。 另外也可以用支持大附件邮箱。 |
 | 19 ncepuzs 2021-12-28 18:46:29 +08:00 这业务场景不是很能看懂，为啥非得以邮件附件的形式发送，上传到云存储然后提供下载链接不是更好吗？ 另外，还有一个问题，不同邮件服务提供商对于接收的邮件附件大小是否有限制，以及限制是多少？ |
 | 20 flyingghost 2021-12-28 18:54:16 +08:00 3 从邮件自身逻辑表达的完整性来讲，一封邮件讲一件事情，因体积关系被迫分拆，那就不应该使用各邮件分别带一部分 pdf 这种缺乏强关联的形式。这种思路是在鼓励漏掉文件。 一定得强调是一个完整逻辑体，邮件标题 [1/3] 、 [2/3] 、 [3/3] 表达关联性，附件使用压缩分卷强迫关联性和完整性。 |
 | 21 fcxxzux 2021-12-28 18:58:39 +08:00 2 如果对于最优解有执着的追求，pdf 数量也就几百个， 可以试试规划求解器，比如 Google OR-Tools 有现成代码 https://developers.google.com/optimization/bin/bin_packing |
 | 22 xuanbg 2021-12-28 22:43:20 +08:00 貌似很复杂，但实际上不就是按发送列表里面的最小附件容量切分文件吗？无非就是不同列表最小值不同罢了。如果是多个文件组合发给多个列表，那么针对不同列表，把多个文件分别打对应列表的最小值分包压缩就是了。 |
| 23 cyrbuzz OP |
 | 26 joApioVVx4M4X6Rf 2021-12-29 10:09:34 +08:00 要发送的 PDF 打个压缩包，把大于 50M 的压缩包分割 |
 | 27 ccraohng 2021-12-29 15:15:45 +08:00 有些邮箱网易还是 qq 是 10mb 限制。 对文件链接没有做安全限制，可以采用文件链接来下载 |
 | 28 wangtian2020 2021-12-29 15:51:36 +08:00 如果是算法题我直接 DFS 梭了 如果是实际应用我直接把所有文件 50MB 分卷压缩 |
 | 29 gablic 2021-12-29 16:15:58 +08:00 跑个题，能不能放云端邮件发链接 |
Select Language