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

jeasun

刚才的code有点问题，应该把大数放在里面
遇到12x7=84这种数就可以得到7而不是12了。

jeasun

回复 26# chong232
哈哈  犀利的西交大学生 非数学专业

jeasun

回复 30# daybreakcx
这个范围。。。
改了看code

jeasun

回复 29# towardWang
问题变成这样的话，复杂多了。10楼的分析就很犀利~~

feuerchop

我给个解法：
6种木块（12,-12,+7,-7,+5,-5），数量任意，假设背包大小W＝N
为了用最小的块数填充，于是从权指最大的12开始，
－（if N>=12）N％12：得到商X和余数Y (X对应12的块数)
－－观察余数Y：范围是从0－11
－－－if Y>=7: Y%7＝X1余Y1
－－－－显然Y1的范围是0－4
－－－if 7>Y>=5: Y%5 = X2于Y2
－－－－显然Y2的范围是0－1
－－－if Y<5: Y的取之范围0－4
－ （if 12>N>=7）N％7
－－余下操作同12
－（if 7>N>=5） N%5
－－余下操作同12
－否则便是1，2，3，4，参考下面的解法
到此为止，我们剩下4个数需要处理：1，2，3，4 （0忽略）
也就是说用最小的块数组合出1，2，3，4把上面得到的余数（Y1，Y2或Y）填满。对应的解法是：
1: （3＊5）＋(－7*2)  (5块)
2：（7－5） （2块）
3：（3＊5）－（12） （4块）
4： （7＊2）－（5＊2） （4块）
加上之前的商便是最后需要的块数。
此解法仅供参考于讨论。

ssa852741

如果b，c都为正，则有12A+7B+5C = w，A = a + 1，B=b-1，C=c-1，则显然|a|+b+c>|A|+B+C=|A|+b+c-2。a|+|b|+|c|最小不成立。

这句看不懂，只明白了|a|+b+c>|A|+b+c-2，但为什么可以导出  |a|+|b|+|c|最小不成立？？

chong232

回复 35# feuerchop


    见我前面的帖子,一样会被考官bs的

chinesedragon

我猜不出来

shhgs

NP

justkain

7 * x + 5 * y  + 12 * z = w;

7 * x' + 5 * y' =  w';

w0 = {-11 ... 11} ==> table[] = |x|+|y| = {...};

w1'   = w % 12,  z1   = w / 12;
w2'   = w1' - 12, z2   = w / 12 + 1;
min(|x| + |y| + |z|)  =  min(table[w1'] + |z1|, table[w2'] + |z2|);