考考大家一道某著名IT的面试题

chong232

类似于背包，但又不同。

有6种木块，数量无穷，大小分别12,-12,+7,-7,+5,-5，给任一正值空间W，从这六种木块中任意选择填充空间，直到正好填满，求使用木块数量最少的一种填充方法。

比如：W=19，这时有很多种填充方法，比如{12, 7},{7,7,5}等等，，但第一种使用木块最少

当时给了我15分钟，，悲剧了

davelv

写程序么？
我的思路是，6个备用模块，取组合，然后相加，得到64--!种数值，然后把和值作为key， 把对应模块重量作为value从小到大，顺序保存到一个表中，然后用二分法查表即可。

chong232

回复 2# davelv


    这个组合，你怎么取，这才是关键的

davelv

我手上有现成的组合函数，STD里面也应该有。从C（0，6）取到C（6，6）全部组合就可以了，一共64 --!种取法。

chong232

回复 4# davelv

   你可以测试一下，我觉得不行啊
  另外，C(6, 0) -- C(6,6)才64，不知道你72怎么来的

davelv

额，总数我算错了，是64个。为什么不行阿，算法上完全没问题。

slay78

W=1怎么填

chong232

回复 6# davelv


    好好想想，这个问题挺复杂的

davelv

请告诉我，我的算法有什么问题吗？
我明白了，数量无穷。。

daybreakcx

负数的块不可能太多，加入负数的块等于在原先的W之上加入所有负数块总和的相反数，换句话说假设你限定的这个负数块最大的阈值是S，那么问题就是求从W到W+S之间的最优值的最小值
比如说你W为17，然后阈值定义为12，那么就是求17到29之间最优值的最小值了
至于阈值定多少，肯定不会很大，对于所有的情况估计值不会超过24，有待具体分析，我只是大概给个范围
最后就是这个问题的最主要问题了，给定正数块12，7，5怎么用最小数目的块构造一个T（W到W+S之间的数），这个用动态规划就可以实现了，假设对于T最小块数是best[T]，那么best = min(best[T - 5], best[T - 7], best[T - 12])，对于无法获得的就设置为无穷大，初始值是best[0] = 0，然后结果就是min(best[i])(W<=i<=W+S)。
同时有一个推论，就是当W很大的时候，并不需要从1算到W，而是貌似只要计算到一个特定值，其它的部分用12（最大的块）填满（以前看到过，不知道有没有记错），这样时间就更快了。
空间上由于对于每个块，我们需要的数值跨越幅度只有12，那么我们只要维护长比12和S的值大一点的数组就行了，然后滚动向前，个人建议取2的幂，比如64这样的，因为循环滚动的时候下标不用%64，只要&63就可以了。
以上个人观点，只是一个大体思路，难免有不对之处，见谅