每次都问大家问题
这次贴个我调试好的 呵呵
#include <iostream.h>
#include <math.h>

int t=0;
int minus=1000;
const int n=5;
int a[n]={15,14,11,10,8};
int x[n]={0};
void Disp()
{
    int sleft=0,sright=0;
    for(int i=0;i<n;i++)
    {
        if(x[i]==0)
            sleft+=a[i];
        else if(x[i]==1)
            sright+=a[i];
    }
        int temp=abs(sleft-sright);
        if(temp<minus)
        {
            minus=temp;
            cout<<"The smallest [color=#ff0000]minus is:"[/color];
            cout<<minus<<endl;
            for(int i=0;i<n;i++)
                cout<<x[i]<<"\t";
            cout<<endl;
        }
}
void BackT(int t)
{
    if(t>=n)
        Disp();
    else
        for(int j=0;j<2;j++)
        {
            x[t]=j;
            BackT(t+1);
        }
}
int main(int argc,int *argv)
{
    BackT(t);
    return 0;
}
感觉每次都要计算，没加约束条件
以后再优化吧
高手也可以帮忙优化下啊，谢了

背包问题:使得得到的一组解的和最接近整个数组元素和的一半.

其实我还可以这样做.
算出一半后直接按贪心就可以得到结果.

//做完排序后

void Solve(int *data,int n,int sum)//数组,元素个数,总和
{
    int i,num=0;//当前选择的元素值和
    for(i=0;i<n;i++)
    {
        if(num+data[i]<=sum/2)
        {
            num+=data[i];
            x[i]=1;//解向量
        }
    }
}

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

int x[100]={0};

void Sort(int data[],int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(data[i]>data[j])
            {
                int temp=data[i];
                data[i]=data[j],data[j]=temp;
            }
        }
    }
    
}
void Solve(int *data,int n,int sum)
{
    int i,num=0;
    for(i=0;i<n;i++)
    {
        if(num+data[i]<=sum/2)
        {
            num+=data[i];
            x[i]=1;
        }
    }
}
int main()
{
    int n;
    int data[100];
    int sum=0;
    srand(time(NULL));
    printf("输入待排序的个数:");
    scanf("%d",&n);
    for(int i = 0 ;i<n;i++)
    {
        data[i]=rand()%100;
       // scanf("%d",&data[i]);
        printf("%-5d",data[i]);
        sum+=data[i];
    }
    Sort(data,n);
    Solve(data,n,sum);
    //printf("\n\n%d\n\n",sum);
    //sum=0;
    for(int i=0;i<n;i++)
    {
        if(x[i]==1)
        {
            printf("%-5d",data[i]);
           // sum+=data[i];

        }
    }
    //printf("\n\n%d\n\n",sum);
    return 0;
}

nuciewth's answer is wrong!!!

diaoxue's answer is correct, but exponential in time complexity.


If nuciewth doesn't believe me, try this data set:
993 588 783 81 374 427 946 697 552 755 831 707

The diff should be 0, but using your algorithm will not get zero, no way!
[color=Black]=====================
[/color][color=Black]I have not found an algorithm not exponential in time complexity yet.
[/color]
Sorry!

[[italic] 本帖最后由 ranchgirl 于 2007-12-8 10:17 编辑 [/italic]]

[url]http://www.[/url]
大家有时间看看啊
谢谢LS

The question is that how to get the least  balance by delimiting the list  so that  get two sum.
my answer is wrong,used the greed algorithm indeed here is not advisability.
i'm sorry!
thanks ,ranchgirl .

n个数x[0..n-1]，假设所有数绝对值的和为S
void resu(int x[],int n){
for(S=0,i=0;i<n;i++) S+=(x[i]<0?-x[i]:x[i]);
for(i=0;i<=S*2;i++) can[0][i]=0;
can[0][S]=1;
for(i=0;i<n;i++){
    for(j=0;j<=S*2;j++) can[(i^1)&1][j]=0;
    for(j=0;j<=S*2;j++) if(can[i&1][j]) can[(i^1)&1][j-x[i]]=1,can[(i^1)&1][j+x[i]]=1;
}
for(i=0;i<=S;i++){
    if(can[n&1][S-i]||can[n&1][S+i]) break;
}
return i;
}