Description
一天，老师在上课的时候提了一个问题，谁要是可以正确解答就有丰厚的礼品可以拿噢！

问题是这样的，老师随机给出了n（n <= 100 ）个数字，可正可负，并且对于每个数字x都满足x>=-2000和x<=2000,同时这n个数的取绝对值的和不会超过5000.让你从中选m(0<m<=n)个数使他们的和尽量接近0（这个和可以是负数），如果有两个值符合条件，那么就选值小的那个输出。




Input

第一行输入一个正整数n，接着的第二行是n个整数。

Output

符合题目要求的最优的值

 

 

Sample Input

3

-1 1 2

4

2 5 -9 6

Sample Output

0

-1

没人关注！！！求解决此题的方法==

这么有难度的题，你都不给分

一道ACM的试题，你发错地方了，即便有人写出正确代码，也可能会超时

再次来到这里，送你小小惊喜，算法有点垃圾，结果还是可以

#include<iostream>
using namespace std;
//穷举法
struct value
{
    int v;
    value *next;
};
class num
{
public:
    num();
    ~num();
    void empty();
    void put(int n);
    void put(int* N,int n);
    const num& operator = (const num&);

    value *val;
    int L;
};
static num my;
const num& SUM(int* N,int L)//求出所有可能的和
{
    int s=0;
    num temp,result;
    value *p=NULL;
    my.empty();
    if(L==1)
    {
        result.put(N,L);
        my=result;
        return my;
    }
    temp=SUM(&N[1],L-1);
    my.empty();
    result=temp;
    result.put(N[0]);
    p=temp.val->next;
    while(p)
    {
        s=N[0]+p->v;
        result.put(s);
        p=p->next;
    }
    my=result;
    return my;
}
void sort(int*& N,int n)//对最初输入的数列进行冒泡排序
{
    int i=0,j=0,temp=0;
    for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(N[j]>N[j+1])
            {
                temp=N[j];
                N[j]=N[j+1];
                N[j+1]=temp;
            }
}
int main()
{
    int m[100];//输入的数据
    int n=0;//数据长度
    int min=2000;//最终的最小值
    int *N=m;
    int i=0;
    num Front;//存放负数的和
    num End;//存放正数的和
    value *F,*E;
    while(cin>>m[n])
        n++;
    sort(N,n);
    while(i<n-1)//找到最大负数的序号
    {
        if(m[i]<0&&m[i+1]>=0)
            break;
        i++;
    }
    if(i!=n-1)//求最小值
    {
        long s;
        Front=SUM(&m[0],i+1);
        End=SUM(&m[i+1],n-i-1);
        F=Front.val->next;
        while(F)
        {
            E=End.val->next;
            while(E)
            {
                s=F->v+E->v;
                s=s<0?-s:s;
                min=min<s?min:s;
                if(min==0)
                    break;
                E=E->next;
            }
            if(min==0)
                break;
            F=F->next;
        }
    }
    else if(m[0]>0)
        min=m[0];
    else
        min=-m[n-1];

    cout<<"min: "<<min;

    return 0;
}

num::num()
{
    val=new value;
    val->next=NULL;
    val->v=-10000;
    L=0;
}
const num& num::operator = (const num& T)
{
    value *p=T.val->next;
    while(p)
    {
        put(p->v);
        p=p->next;
    }
    return *this;
}
num::~num()
{
    empty();
    delete val;
}
void num::empty()
{
    value *p=val->next,*pre;
    while(p)
    {
        pre=p;
        p=p->next;
        delete pre;
        L--;
    }
    val->next=NULL;
}
void num::put(int n)
{
    value *pre=new value,*p=val->next,*q=val;
    pre->v=n;
    while(p)
    {
        if(p->v==n)
            break;
        else if(p->v>n)
        {
            pre->next=p;
            q->next=pre;
            break;
        }
        else
        {
            q=p;
            p=p->next;
        }
    }
    if(!p)
    {
        p=pre;
        p->next=NULL;
        q->next=p;
    }
    L++;
}
void num::put(int* N,int n)
{
    int i=0;
    while(i<n)
    {
        put(N[i]);
        i++;
    }
}

[ 本帖最后由 nicum 于 2011-9-20 18:45 编辑 ]

楼主笑纳，我可调试了一下午呀

我觉得这个dfs和暴力必然超时的说，dp应该正解