不锈钢砝码的调选规则分享 上海众渊砝码厂规划发展 2017.08.04 
上海众渊砝码厂总结了不锈钢砝码的一些挑选规则。 众渊品质，。 现在将这些挑选规则分享给大家： 问题描述： n个砝码称一个质量为m的物体，求少需要的砝码数。n范围为[1,30],m及每个砝码的质量在int范围内。 解题思路： 易想出的方法是枚举可能情况，把和为m的使用砝码数少的情况挑选出来。显然多会有2^30种情况可供枚举。然后在时限为1秒的情况下，这种方法毫无疑问会时。 如何优化呢？既然不能枚举，我就一半一半枚举。枚举一半多2^15种情况，不妨把前一半砝码可能组成情况放在数组A中，后一半可能情况放在数组B中，然后按照每种情况能够称的重量数对B数组进行快速排序，此步骤多耗时15*2^15（nlgn）。然后对于A中的每一种情况，到B数组中进行二分查找，如果能找到，则新少砝码数，耗时多也是15*2^15（nlgn），总得时间复杂度为n*2^n，在n大为30的情况下不会时。 上海众渊砝码厂。 众渊品质，。 |
