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

chong232

回复 68# shymn


    w如果是负的话,就取正,再按你的方法计算,结果全部取反, 但｜a｜＋｜b｜＋｜c｜是不变的

codekitten

直接用组合数学的知识，设一个母函数，理论上可以解出所有W的最小组合。。。

jhkwei

我的思想是这样的，要能表达所有的数，肯定要1，2，3，4
1=5+5+5-7-7   
2=7-5
3=5+5-7
4=7+7-5-5
这四项已经是最小解了

再做，w=a*12+b*7+c*5+d；a,b,c,d为非负数
若d=0结束；
不为0
先求max (a),再求a,b,是0还是1；
再把d以上面的1，2，3，4代入，
再看看能不能消除把带“-”这项;
同样还要注意-1,-2,-3,-4问题，
看c是否为1；为1，置c=0,b=b+1;再求d,d 在此为负数


主要是比较正负数d那个消项更多；

如果把d看做一整体，这项只可能增加项，不可能减去项也就是w在些基础上只能增加项不会减少项；
应该求出来的解就是最小项了

ricks_wu

mark
等我看完了编程艺术的算法再来

abc3w

回复 7# slay78


    +5+5+5-7-7

倒数第二位

回复 23# jeasun


   这个必须顶起来！！！
数学大神

saintdragon

虽然不写程序，但佩服之极！
尤其是搞算法的各位和数学精通的各位！

davelv

直接用组合数学的知识，设一个母函数，理论上可以解出所有W的最小组合。。。
codekitten 发表于 2010-08-21 17:00

生成函数一般都是用来计算解的个数，我目前还没见到它用来计算最优解。也可能是我了解的比较少的缘故，不知这位仁兄可否把自己的观点分享一下？

fanronghua

告诉他四个字（背包算法）