第一次有人表扬我，我可是遇到编程科目就挂红灯的主啊！

声明：题目要求重量可以到100000，本程序限定在int内（测试者可以改动）
只提供一组测试数据测试，需要多组，测试者加个循环修改
本程序提供测试之用，不一定正确
[CODE]
#include "stdio.h"
#include "math.h"
#include "malloc.h"

int d_value;
int *array,size,sum=0;

void Subset(int i,int total)
{
int s_total=0;

for(;i<size;i++)
{
s_total=total+array[i];
if( d_value > (int) fabs(sum-2*s_total) )
d_value = (int) fabs(sum-2*s_total);
if(i<size-1)
Subset(i+1,s_total);
s_total=0;
}
}

int main()
{
int i,total=0;

printf("please input the num of test data:\n");
scanf("%d",&size);
array=(int *) malloc ( sizeof(int)*size );
printf("pleade input test data:\n");
for(i=0;i<size;i++)
{
scanf("%d",array+i);
sum+=array[i];
}
d_value=sum;
for(i=0;i<size;i++)
{
Subset(i,total);
total=0;
}
printf("%d\n",d_value);
free(array);

return 0;
}

[/CODE]

先排一下序会 简单的多

还是看不懂！！
？？？

我感觉不用像楼上的，
你可以将前N项和N-1项比较呀

版主老大您的程序,俺检验到现在，还没发现毛病呢!
我也编了个这道题的程序，专门用来检测版主您的程序，感动吧
呵呵，不过,我算法很烂,当时只是想用来检测而已,没仔细想算法.
现在也把它贴上去，提供小数字的检验，大数字这程序检验不了，算法太过垃圾!
/*
程序辅助生成一个长为n的0-1串,开始为111111;灼次减1至000000;每次生成两个和sum1(1相加),sum2(0相加);比较最小即可得到,当然,这个算法较烂,实现时间要很长，检验大数的时候,不可忍受!
*/
#include <stdio.h>
int main()
{
int num,i,j,k,tag=0,sum1=0,sum2=0,flag=0,temp,minous;
short *memo=NULL;
int *stone_weight=NULL;
printf("Please input the number of the stones:\n");
scanf("%d",&num);
memo=(short *)malloc(sizeof(short)*num);
for(i=0;i<num;i++)
memo[i]=1;
stone_weight=(int *)malloc(sizeof(int)*num);
printf("Now please enter the weight of the stones:\n");
for(i=0;i<num;i++)
scanf("%d",&stone_weight[i]);
while(1)
{
for(j=i-1;i>-1;j--)
{
if(memo[j]==1)
{
memo[j]=0;
for(k=j+1;k<num;k++)
memo[k]=1-memo[k];
break;
}
}
for(i=0;i<num;i++)
if(memo[i]==1)
break;
else tag++;
if(tag==num)
break;
tag=0;
for(i=0;i<num;i++)
{
if(memo[i]==1)
sum1+=stone_weight[i];
else
sum2+=stone_weight[i];
}
if(flag==0)
{
minous=sum2-sum1>0?sum2-sum1:sum1-sum2;
flag=1;
}
else
{
temp=sum2-sum1>0?sum2-sum1:sum1-sum2;
minous=minous>temp?temp:minous;
}
sum1=sum2=0;
}
printf("%d\n",minous);
free(memo);
free(stone_weight);
getch();
return 0;

}


soft_wind 实在是辛苦啦 ，记特等功一次


----------胡锦涛

大家看一下我的想法:
假设sum=(-1)^x1a1+(-1)^x2a2+...+(-1)^xnan
其中xn是-1的指数,an是第n堆石头的重量,且xn的取值是1或2.
那问题就是求sum的最小值,具体看一下每个xn的取值.

这本来是条数学问题,但我就不会用数学的方法解决了.
考虑到计算机的速度,我们完全可以用穷举法,将所有的sum求出来,再找到最小值.