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

davelv

想到一个方法，先求得w=[1,12]的最佳取法。
当w>12时，每次递减12直至剩余的空间在[1,12]的范围内，然后再从表中获取对应取法。

daybreakcx

想到一个方法，先求得w=[1,12]的最佳取法。
当w>12时，每次递减12直至剩余的空间在[1,12]的范围内，然后再 ...
davelv 发表于 2010-08-18 10:25

贪心是无法总得到最优解的，比如我给你个14
按照你的方法，你先减去最大的，也就是减去12，剩下2，然后构造2最快的是用两个，就是7和-5，总共用了3个
实际上我两个7就搞定了。

chong232

回复 12# daybreakcx


    当时我回答的也是贪心，不过先判断是否是12,7,5的倍数，再判断是否可以最大可能的填充，即依次尝试填充12,7,5，最后只剩下W=1,2,3,4这四种情况了，可以穷举找出

   但我保证不了是最优，面试官不置可否，，悲剧

daybreakcx

回复 13# chong232


    考官不置可否是经常的事情，这个问题还算比较经典的动态规划，贪心可以局部进行时间和空间的增强，但是要想获得最优解贪心不行

davelv

总觉得应该有个值M，当W>M时，最优(W%M)+W/M*最优(M) ==最优(W)

chong232

回复 14# daybreakcx

嗯，先想到了动态规划，但没有思路，就直接贪心了，你的思路不错，呵呵，估计换成你就过关了

ancjf

先求得w=[1,23]的最佳取法。
当w>23时，每次递减24直至剩余的空间在[1,23]的范围内，然后再从表中获取对应取法

benjiam

错了 这个解不是最优的

daybreakcx

先求得w=[1,23]的最佳取法。
当w>23时，每次递减24直至剩余的空间在[1,23]的范围内，然后再从表中获取对应 ...
ancjf 发表于 2010-08-18 14:02

反例：W=50
你的方法：50-48=2，2用7-5，48即12*4，总4+2=6个数
实际上：12+12+12+7+7=50，总5个数

benjiam

反例：W=50
你的方法：50-48=2，2用7-5，48即12*4，总4+2=6个数
实际上：12+12+12+7+7=50，总5个数
daybreakcx 发表于 2010-08-18 14:19

    suoyi  1-12
he 1-23