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

btdm123

这是个退化的01背包问题，你就是硬算，时间复杂度也就是N取2的组合，即n^2

btdm123

描述算法一般用伪码，不纠缠于语言细节。关键是要能通过数学证明

b02213131

修正一下，复杂度是O（n）,先用2分法找出一个最接近的数，这个数和最小的数之间形成一个区间，我们从两头分 ...
btdm123 发表于 2011-10-08 11:49

这样写相当于贪心算法，这个题的话，已有条件不能证明其正确性（而且绝对可以证明你算法的不正确性）
因为你找的第一个数，就不一定是肯定包含在最终结果中的
这样做最多可以找出个近似解

btdm123

这样写相当于贪心算法，这个题的话，已有条件不能证明其正确性（而且绝对可以证明你算法的不正确性）
...
b02213131 发表于 2011-10-09 11:22

可以证明阿。先取一个最接近M的更大的数X [j] ,和最小的数X [0] 形成一个区间X ［0,j］, 假设存在最优解，其中一个点落在[0,j]区间外,那么这个点可以换成X[j],
变得更优，因此假设不成立。
X [0] + X [j] >M,
如果 X [0 ] + X[j-1] >M 那么X[0]和X[j－1]是较优的解，可以证明如果还有更优的解，必落在[0,j－1]内；
如果X [0 ] + X[j-1] <M 那么在X [0,j]与X［0,j－1］之中选一个较优的解，如果还有更优的解，必落在[1,j]内；
类似这么证明，可以一步步缩小范围。

b02213131

可以证明阿。先取一个最接近M的更大的数X [j] ,和最小的数X [0] 形成一个区间X ［0,j］, 假设存在最优解 ...
btdm123 发表于 2011-10-09 11:49

不好意思，以为你找的第一个数就拿到最终解里面去了

shang2010

DP题？？

scanmiss

#include "stdafx.h"
#include <math.h>

#define N 10

int _tmain(int argc, _TCHAR* argv[])
{
        float X[N] = {0,1,2,3,4,5,6,7,8, 9};
        int n = 5;
        float M = 5.1;
        int start=0;
        int i;

        if (n >= N)
        {
                //print all
                ;
        }
        else
        {
                for (i=n;  i<N; i++)
                {
                        if (abs(X[i] - M) < abs(X[start] - M))
                        {
                                start = i-n;
                        }
                }

                for (i = start; i< start+n; i++)
                {
                        printf(" %f ", X[i]);
                }
        }
        getchar();
        return 0;
}

算法长度应该是N吧..

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) {
    //n == 0 && left=true, 这个节点就是left_most节点。
    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

李大双

好滴0

回复 1# snowboy9859


    我想的没大家这么复杂 就是遍历一次 用xi和x[i+n]分别与X相减  然后比较两者的绝对值 知道xi的大于x[i+N]的停止比较  所要求的数就是这两者之间的  
  
   不知道对不对哈