本
文
摘
要
导言
在最近的生活中,我遇到这样的烦恼——家中物品品类多杂尺寸不一,厨房的锅碗瓢盆、油盐酱醋;工作室的洗漱护肤、家用电器;卧室的衣物鞋袜、床单被罩。如果直接地将其放在橱柜里,一则摆放时,杂乱无序会影响心情;二则使用时,低效翻找又将心情影响一次。因此,产生了在橱柜里放置进一步细分的收纳盒,以还一个张弛有度的生活空间。
但是,在精密测量了橱柜内的尺寸准备去网购时,发现一系列的致命的问题——并不能找到一个盒子的尺寸正正好好地契合一个橱柜隔档的空间。。。此外,我家每个橱柜的隔档空间并不一致!并且更头疼的是,每一店家的盒子都有各自的多个尺寸可选,而且不同店的盒子的尺寸大小也不尽相同。
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到此为止,整个家居收纳盒的组合问题就可解了。我也是通过上述的方法,快速得到了家里三三一十九个不同尺寸的橱柜空间,每个空间的收纳盒最佳组合方案,以及每种收纳盒的购买数量了。
结语
上述的完整的代码地址。其实关于这个问题,我做了许多的简化以限定了搜索空间的大小,实际上这个问题的搜索空间是可以更高维的。在这里,图一乐,将这个生活中的问题记录下来,如有有缘人看到,也感兴趣,欢迎沟通交流。