本
文
摘
要
导言
在最近的生活中，我遇到这样的烦恼——家中物品品类多杂尺寸不一，厨房的锅碗瓢盆、油盐酱醋；工作室的洗漱护肤、家用电器；卧室的衣物鞋袜、床单被罩。如果直接地将其放在橱柜里，一则摆放时，杂乱无序会影响心情；二则使用时，低效翻找又将心情影响一次。因此，产生了在橱柜里放置进一步细分的收纳盒，以还一个张弛有度的生活空间。
但是，在精密测量了橱柜内的尺寸准备去网购时，发现一系列的致命的问题——并不能找到一个盒子的尺寸正正好好地契合一个橱柜隔档的空间。。。此外，我家每个橱柜的隔档空间并不一致！并且更头疼的是，每一店家的盒子都有各自的多个尺寸可选，而且不同店的盒子的尺寸大小也不尽相同。
JosephJoseph 厨房清洁工具 餐厨收纳盒大号 灰色 大号知乎¥180.00去购买我家有三三一十九个不同尺寸的橱柜空间。而即使只考虑盒子的尺寸因素，在活跃在互联网上可供选择的盒子也有九九三万三个数量。这怎么玩？？
我相信每一个认真生活的人都会遇到这样的问题吧？十分好奇你们是怎么解的呢？
而我——选择了组合规划的解法，即将该问题建模为一个在离散空间中寻找最优组合的问题。
建模
将橱柜空间编码所谓编码，就是给一个ID，或者是key值，如下表所示，我基于目标位置进行编号。而后，测量记录每个橱柜空间的长宽高。由于使用收纳盒是为了对每个橱柜空间作空间上细分，因此我还给定了每个空间的空间分割方式，比如在高度轴分成两层，或是在宽度轴上分成两部分。
将可选盒子编码盒子的编码则要简单一些。直接使用 *** 数字进行编号，每个盒子记录其尺寸信息。当然，如果对于盒子有尺寸之外的要求，这里可以考虑盒子的其他属性。也可以像我一样，在筛选盒子入编码时时就把其他诸如颜色、款式的属性考虑了，以保证无论解出的是何种盒子组合，都可以直接买。
解法
如果直接上组合，那时间复杂度和空间复杂度都是不优雅的。在此，出于一致性美观的考虑，实际上需要各层使用一样的盒子组合。基于此，便可一个简化——先考虑组合组成一层的可行性，再考虑多层组合后的最优。
可以看到，在橱柜空间编码时，我已经设定了，每个目标空间分成了若干层，每层由m个盒子组成。 因此，这里我便可以先考虑AnmA_{n}^{m} （n为可选盒子的数量）的可行性，即长和宽是否超出目标空间的尺寸。
用Python代码实现可以使用itertools.combinations_with_replacement 获得排列组合的空间，然后遍历判断可行性即可。
all_combinations = find_all_combinations(idx_arry, most_num) for combin in all_combinations: check_available(combin, available_size_table, target_size, use_cost_type)到这里，通过对该离散空间和组合方式的限定，已经缩小了组合空间，机智避免了维数爆炸。
那么就剩下一个问题——最优如何评定？其实也就是，cost function如何设计？
这个见仁见智的设计会导致不同的最优结果的评定。
这里抛砖引玉，我使用的最简单的人工规则设计法——核心思想是，长宽高中任一维度超过目标空间的尺寸，则直接给个最大值，否则尺寸越接近越好。由于长宽高的契合度的重要性并不一致，对每个维度给了不同的权重。
def cost_fun(target, use_size): cost = 0 # long if target[0] < use_size[0]: return INT_MAX else: cost = cost + weight_height * (target[0] - use_size[0]) # width if target[1] < use_size[1]: return INT_MAX else: cost = cost + weight_width * (target[1] - use_size[1]) # hight if target[2] < use_size[2]: return INT_MAX else: cost = cost + weight_height * (target[2] - use_size[2]) return cost到此为止，整个家居收纳盒的组合问题就可解了。我也是通过上述的方法，快速得到了家里三三一十九个不同尺寸的橱柜空间，每个空间的收纳盒最佳组合方案，以及每种收纳盒的购买数量了。
结语
上述的完整的代码地址。其实关于这个问题，我做了许多的简化以限定了搜索空间的大小，实际上这个问题的搜索空间是可以更高维的。在这里，图一乐，将这个生活中的问题记录下来，如有有缘人看到，也感兴趣，欢迎沟通交流。
