搜狐2012牛逼笔试题，至今无思路，求牛人指点

三月廿七

题目出的牛B，干活的时候指不定傻B呢

btdm123

还在纠结这个题阿，用haskell写会比较简练

leizisdu

给出的序列是实数序列，怎么应用”0/1背包问题“的算法？{:3_183:}

siseniao

必定是二分法

leizisdu

回复 37# ggzwtj

我说一下我的想法：
1、用0-1背包求出比M小的最大的选取方法。
2、设给定的N个数的和为SUM，那么再用一次0-1背包算法求出（SUM-M）的取法，那么没取的数就是大于M的情况下最接近M的取法。
综合1、2就可以找到最接近的取法。

顶{:3_190:}

leizisdu

回复 38# ggzwtj
“0/1背包问题”中的质量和价值都可以是实数。有些算法只能处理质量是整数的情况，但也有些算法没有这个限制。{:3_183:}

keytounix

回复 1# snowboy9859
求答案

snowboy9859

回复 47# keytounix


    无答案，我至今没弄明白，以其昏昏使人昭昭的事我不做，请看本贴牛人回复

keytounix

回复 1# snowboy9859


    我想了一个星期终于吧这个问题抽象成简单的NP问题了

和你分享一下

1.  集合 Sn={x1,x2,...xn}

首先, 检测Sn中是否存在=M的数，
        若存在，则是就是M了，最简单。
        若不存在==M的数，则
             检测 Sn中是否存在小于M的数，
             若无，则说明M是最小的，那就找Sn中最小的即是答案；
              若有，  
                   检测 Sn中是否存在大于M的数，
                          若无，则是简单的NP问题，设求解方法是         np_func(M);
                          若有大于M的数，最好了，设Sn中<M的数据组成的集合为S1，其中的最大值是S1_Max
                                      设Sn中>M的数据组成的集合为S2,其中的最小值是S2_Min
                                       则对S1中所有数抽象成NP问题

                                       #define min(a,b) ((a)<=(b)?(a)b))

                                      int the_var=fabs(S1_Max-M);//存储与M最小的组合

                                       for(i=S1_Max;i++;i<=S2_Min)
                                           {
                                              the_var=min(the_var,np_func(i));
                                           }

hbmhalley

回复 13# btdm123


    首先装箱问题是NPC的，你的任何多项式算法一定有问题
    你在缩小问题规模的时候好好想想 你的问题规模真的可以放心的缩小了么？当x[0]+x[j]<M的时候 x[j]一定选么？{3,3,3,4},9  你的算法跑出来是多少？

    不要拿“接近”说事，“接近”可以用迭代精度的方法多项式规约到装箱问题

    个人觉得只能把它当NPC问题解决