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

btdm123

用2分法，lnN

mfkwwgi

及其复杂，我连题都没有读懂呢。

btdm123

修正一下，复杂度是O（n）,先用2分法找出一个最接近的数，这个数和最小的数之间形成一个区间，我们从两头分别取数，试探有没有更好的解，有的话，形成更小的区间，递归

无法如愿

回复 13# btdm123


    这个类似 背包问题
可能存在多组解，
你这样至多得到一个解，
这个解可能是局部最优解，
但很可能不是全局最优解

zhanglistar

回复 1# snowboy9859


    01背包问题的变形。   
    01背包可以使用动态规划在O（n^2）内解决。

ruslin

类似背包问题，满二叉树结构。

原理：
比如一共有N个数，参照值是M。那么对于第N个数来说，只有两种选择要么不用这个数，要么就用这个数。
不用的情况就是前N-1个数任意几个和最接近M的值是：f(N-1，M)， 前N-1个数。
用的情况先算出前N-1个数任意几个和最接近M-value(N)的值是：f(N-1，M-value(N))， value(N)显然就是第N个数的值，既然用了它就要把它减了,然后把算出来的值加上value(N)跟不用的情况算出来的值同M相比较，看谁更接近。
n-1，n-2，。。。3,2,1原理都一样。
到了第1个数，求它和某个值x的最接近的值就是两个可能：可以选择它加上value(1)，或者不选择它加上(0)。但是left_most节点必须选择。

时间复杂度O(2^n)

存在问题：
1。 递归调用，如果N太大,会调用 2^n - 1次，可能会栈溢出，不知能否去掉递归。
2。 考虑到题目是顺序排列的，不知能否优化，暂时没想到。
3。 测试了几组数据是正常工作的。不保证一定正确。


#include <stdio.h>
#include <stdlib.h>

int a[10] = {4, 10, 30, 33, 39, 58, 200, 300, 400, 1000};
int m = 100;


int fun(int n, int value, bool left) {

  if (n == 0) {
    printf("left = %d\n", left);
    if (!left && abs(0 - value) < abs(a[0] - value)) {
       return 0;
    } else {
       return a[0];
    }
  }

  int value1 = fun(n-1, value, left ? true : false);
  int value2 = fun(n-1, value-a[n], false);

  //printf("fun n = %d, value = %d, value1 = %d, value2 = %d\n", n, value, value1, value2);

  if (abs(value2 + a[n] - value) < abs(value1 - value)) {
    printf("fun n = %d, value = %d, value2 = %d, a[%d] = %d, res = %d\n", n, value, value2, n, a[n], value2 + a[n]);
    return value2 + a[n];
  } else {
    printf("fun n = %d, value = %d, res = %d\n", n, value, value1);
    return value1;
  }

}


int main() {
  int res = fun(sizeof(a)/sizeof(a[0])-1, m, true);

  printf("res = %d\n", res);
  return 0;
}


root@ubuntu:/work# ./a.out | grep "value = 100"
fun n = 1, value = 100, value2 = 4, a[1] = 10, res = 14
fun n = 2, value = 100, value2 = 14, a[2] = 30, res = 44
fun n = 3, value = 100, value2 = 44, a[3] = 33, res = 77
fun n = 4, value = 100, value2 = 63, a[4] = 39, res = 102
fun n = 5, value = 100, value2 = 43, a[5] = 58, res = 101
fun n = 6, value = 100, res = 101
fun n = 7, value = 100, res = 101
fun n = 8, value = 100, res = 101
fun n = 9, value = 100, res = 101

btdm123

回复  btdm123


    这个类似 背包问题
可能存在多组解，
你这样至多得到一个解，
这个解可能是局部 ...
无法如愿 发表于 2011-10-08 14:00

没错，是个动态规划问题，但不需要回朔。简单描述是这样的：
设数组X从0到n， 要求最接近M。
［code］
先取小于M的最大数X[j],i=0,解一定存在于X[0]至X[j]中，规模函数为f(i,j)
if X[i+0]+X[j]<M
then  如有更优解，必存在于X[i＋1],X[j]之间，规模函数变为f(i+1,j);

if X[i+1]+X[j]>M
then 和X［i］+X[j]比较，记录更接近于M的解，
如果还有更优的解，必存在于f(i,j-1)之中
[/code]
不断递归，直到j==i

koolcoy

我怎么看怎么觉得这就是个背包问题呢~

第一步找出和比M小的一组数，并且求出这个和能取到的最大值，这是一个标准的背包问题。
第二步找到和比M大的一组数，并且求出这个和能取到的最小值，这不是一个背包问题，但是用类似背包问题的那种dp就能解决。
第三步，比较第一步和第二步计算出的结果

davelv

生成函数无误，时间复杂度约O(n^2)
参考这里：
http://blog.csdn.net/davelv/article/details/6481468

davelv

哦，昨天忘记说了。这是个变形的0-1背包问题。