实际项目中同事提出来需要解决这么一个子问题：我们有一堆大小不同的小图，希望可以把它们拼接起来成为几张大小相同的大图，尽量保持大图的数量越少越好。
这个问题挺有趣的，当时直觉上判断这个是NP的，应该是很难快速地得到最优解的。同时也觉得这个问题抽象出来之后应该是有被仔细研究过的。周末有点时间RE-Search了一下，果然这是一个很经典的问题，叫Bin Packing，也确实是NP的。
准确的说，Bin Packing是开头那个问题的一维版本，开头的问题是2D Bin Packing的一个特殊情况。继续走到更高维度去，比如3D的Bin Packing就很接近于集装箱装货的场景了，这个问题的名字可能也就是这么来的。
Bin Packing 在 wiki 上有很详细的介绍: 给定N个数值，分成K份，每个分区的和不大于B，K最小的解就是最优解。这个问题也分为两个版本: 在线(online) 的版本，和离线(offline)的版本。在线的版本是特殊情况，也就是数值是逐个给出的，每次拿到一个新的数值之后，需要决定把它放到哪个Bin里面，或者是新开一个Bin。常用的好实现的算法都是近似解，有很多人做了数学上的证明说一个算法能保证得到的解的质量。对于离线版本，基本上就是从大到小排序之后跑一个在线版本的算法，就可以提升解的质量。
挺有趣的是，这个问题还是在被研究。特别是在对应的exact algorithm这块。wiki上提到的最新的版本，居然是2013年发在IJCAI上的文章。粗看了一下，是从Branch-and-cut这套方法做的，没有找到开源的实现，估计得是比较好的solver才有的了。
到这为止还只是讨论的一维的Bin Packing。实际2D的情形更加复杂，但是也更加实用。找到了一篇2010年的Survey对这个问题做了很好的一个总结。对于这个问题被研究的程度，文章的标题说明了一切: A Thousand Ways to Pack the Bin – A Practical Approach to Two-Dimensional Rectangle Bin Packing。Github有对应的代码实现: https://github.com/juj/RectangleBinPack
再次感觉到很多时候，实践中遇到的问题，合适地抽象出来之后，很有可能只是某个很经典问题的特例。新的问题并不多。