2013微软笔试题：找数组加减运算的结果和目标元素最小距离

上周六参加了一场微软秋令营的笔试，感觉最后一道笔试题出的蛮有水平。
题目如下：
给定一个数字的序列，例如：1、2、3、4、5、6、7，序列中随意的添加“+"或者”-“，使得最后的运算结果，跟给定的数值，例如：9，之间的差值最小。请给出符合要求的结果串，例如：1 + 3 + 4 + 5 + 6 - 7 - 2
拿到这道题目，本人的第一反应就是对于给定的序列做和然后减去目标数值之后除以2获得一个数值x，然后再去原来的序列中查找和为x的序列，就是应该减去的序列。但是困难就又出现我们如何在一个序列中找出和为x的所有序列呢？
这个很容易让我联想到一个经典的动态规划问题，背包问题：
有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件 物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品， 那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容 量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

在这里我们要得到和最接近x的目标元素的序列，实际上就可以当作是容量为x的大小的一个背包，我们有质量不等n个元素，将其中m个元素放入包，使得他们的和不超过x，并且达到最大值。
下面是我的解法：

/*************************************************************************
    > File Name: test87.cpp
    > Author: dongdaoxiang
    > Func: Find Min Gap
    > Mail: [e-mail]
    > Created Time: 2013年06月26日 星期三 21时54分13秒
 ************************************************************************/
#include<iostream>
#include<string>
#include<algorithm>
#include<sstream>
#include<vector>
using namespace std;

void init(int *a, int m, int n)
{
    int i = 0;
    for(i = 0; i < m*n; i++)
    {
        a[i] = 0;
    }
}

inline string IntToString(int a) //整形到字符串的转换
{
    string dest;
    stringstream ss;
    ss << a;
    ss >> dest;
    return dest;
}

inline int Max(const int a, const int b)
{
    return a > b ? a : b;
}

int OptResult(const vector<int> &arr, const int dest, int index) //背包问题，获取辅助数组元素值函数
{
    if(index < 0)
    {
        return 0;
    }
    if(index == 0)
    {
        if(arr[index] <= dest)
            return arr[index];
        else
            return 0;
    }
    if(arr[index] > dest)
    {
        return OptResult(arr, dest, index - 1);
    }
    else
    {
        return Max(OptResult(arr, dest - arr[index], index - 1) + arr[index], OptResult(arr, dest, index - 1));
    }
}

void Find(vector<int> &minus, vector<int> &arr, int *a, int index, int wight, int size) //回溯找到最优解
{
    if(a[size * index + wight] == 0)
        return;
    if(a[size * index + wight] < arr[index])
        Find(minus, arr, a, index - 1, wight, size);
    else
    {
        if(a[size * index + wight] - arr[index] == 0)
        {
            minus.push_back(arr[index]);
            arr[index] = -1;
            return;
        }
        if(a[size * index + wight] - arr[index] == a[(index - 1)*size + wight - arr[index]])
        {
            minus.push_back(arr[index]);
            int temp = arr[index];
            arr[index] = -1;
            Find(minus, arr, a, index - 1, wight - temp, size);
        }
        else if(a[index * size + wight] == a[(index - 1) * size + wight])
        {
            Find(minus,arr,a,index - 1, wight, size);
        }
    }
}


void Bag(vector<int> &arr, const int dest, vector<int> &minus)
{
    int m = arr.size();
    int n = dest;
    int c[m * (n + 1)];
    init(c, m, n + 1);
    int i = 0;
    int j = 0;
    for(i = 0; i < arr.size(); i++)
    {
        for(j = 0; j <= dest; j++)
        {
            c[i * (dest + 1) + j ] = OptResult(arr, j, i);
            cout << c[i * (dest+ 1) + j] << " ";
        }
        cout << endl;
    }
    cout << "dest: " << dest << endl;
    Find(minus, arr, c, arr.size() - 1, dest, n + 1);
}


void MiniGap(vector<int> &ivec, const int dest, string &result)
{
    if(ivec.empty())
    {
        return;
    }

    if(ivec.size() == 1)
    {
        result = IntToString(ivec[0]);
    }

    size_t i = 0;
    int sum = 0;
    vector<int> minus;
    for(i = 0; i != ivec.size(); i++)
    {
        sum += ivec[i];
    }
    sort(ivec.begin(), ivec.end());
    int temp = (sum - dest + 1) >> 1;
    if(temp < 0)
    {
        return;
    }
    else
    {
        Bag(ivec, temp, minus);
    }
    for(i = 0; i != minus.size(); i++)
    {
        result += '-';
        result += IntToString(minus[i]);
    }
}

int main()
{
    vector<int> ivec;//给定的元素序列
    int i = 0;
    int dest = -27; //目标元素的数值
    string result;
    string result2;//结果串
    for( i = 1; i <= 8; i++)
    {
        ivec.push_back(i + 6);
    }
    MiniGap(ivec, dest, result);
    for(i = 0; i < 8; i++)
    {
        if(ivec[i] != -1)
        {
            result2 += IntToString(ivec[i]);
            result2 += '+';
        }
    }
    string::iterator it = result2.end() - 1;
    result2.erase(it);
    result2 += result;
    cout << result2 << endl;
    return 0;
}

可以得到如下的结果：

8+9+11-14-13-12-10-7