这是一个创建于 1066 天前的主题，其中的信息可能已经有所发展或是发生改变。
老哥们求教，给难住了= =。
场景是这样的：
有很多 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
czfy 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