瀑布式照片墙排版算法研究

产品中有一个个人照片墙的页面，设计想出了瀑布式的版式，大家都认为视觉效果不错，下面的原型图大致说明了这种版式的效果。

照片是用户自己上传的，所以照片的尺寸是不确定的。当然我们也可以完全不在意图片的尺寸，可以用css把它们排版成版式要求的样子。不过由于图片的宽高比并不确定，如何安排每一张图的位置就成为需要解决的关键问题。

按序号奇偶性分发图片

最简单也最直观的方法是直接把图片编号，奇数号放入左栏，偶数号放入右栏。如果用户每张图片的宽高比都差不多，可以用这种方法取得比较好的效果。但是这种方法存在两栏高度差异巨大的风险，如果恰好用户上传照片是横、竖、横、竖……这种顺序，那就会出现左矮右高的悲剧。

向较矮栏分发图片

针对上面方法出现的问题，一个简单的优化是直接在每次置入图片前计算左右两栏各自的高度，然后将图片置入较矮的一栏。因为只有图片加载出来才能知道它的高度，所以不能像前面的方法那样一股脑儿全塞进左右栏中，需要等图片载成功后一张一张放入。

正因为要等图片加载成功才放入，所以这种算法是不稳定的，可能每次刷新时图片的顺序都不一样。另外这个算法提供的只是一个小改进，它并不能得出让左右栏高度最接近的方案，在出现特长图的时候问题更为明显。

动态规划解

有没有可能找到一个最优的方案，保证所有图片置入后，左右栏高度最为接近呢？图片的宽度是固定的，变化的只会是高度，问题可以转化为一个抽象的数学问题：将一个由n个整数元素构成的集合N，划分成两个子集A和B，确保N = A + B，求能使SUM(A)最为接近SUM(B)的划分方法。

把问题抽象化之后就比较好解了。根据前述条件可知SUM(B) = SUM(N) - SUM(A)，要求SUM(A)最为接近SUM(B)，不妨假设SUM(A) ≤ SUM(N)/2 ≤ SUM(B)，那么问题就变成了从集合N中选中若干元素构成集合A，使SUM(A)最为接近SUM(N)/2。这下问题变得很眼熟了吧，俨然就是背包问题啊。

背包问题及其各种变种的详细解法请参考Tianyi Cui写的《背包问题九讲》，这里我只对这个问题求解。不妨先考虑集合N中的第一个元素N[1]，需要决定把它放入或者不放入集合A中，从而使得SUM(A)最接近SUM(N)/2。如果不把N[1]放入集合，那么需要知道对于第二到第n个元素，能构成的最接近SUM(N)/2的和是多少；而如果把N[1]放入集合中，则需要知道对于第二到第n个元素，能构成的最接近SUM(N)/2 - N[1]的和是多少。通过比较就可以确定是否应该放入N[1]。同理，对于第二个元素N[2]，决策前需要比较的是第三到第n个元素的放置加和情况。直到第n个元素，放入或者不放一目了然。当记录下这些放置组合之后，可以找出最优决策链。

总结

奇偶分发法最为简单，也最容易遇到麻烦，只适合所有图片尺寸相同（比如Instagram）的情况下使用。

向最矮栏分发法虽然无法取得最优解，但也能得到不错的结果。因为无需提前知晓全部图片的尺寸，比较适合用在分批无限载入的流式布局中。这种方法的最大问题在于图片载入顺序对排版结果影响巨大，如果先成功载入短图（短图一般比较小，很容易先完成载入），较均匀地分发后方才载入长图，可能出现严重的分配不均情况，可以由服务器端下发图片尺寸信息来帮助缓解这一情况，从长到短分发能取得更好的效果。

动态规划的方法可以求得最优解，但算法的复杂度相对较高，而且需要知道所有图片的高度之后才能开始运行，不适合用在图片可以加载更多的流式场景。当然，如果服务器端能提供图片尺寸信息，就能绕过上述缺点。

前面提供了三种实现思路。最后可以看一下例子程序。