用0-1统治世界!
声明:题目要求重量可以到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]