关于回溯算法的一道题
求助关于回溯算法的一道题
题目是本来有一个自然数数组，这里是1-500.然后在这个数组里面选取10个数，让这10个数的任意（共2^10次）组合所加的和都不想等。
我的想法就是申请一个全局数列，然后分别从500开始试探添加元素，不符合条件，就换下一个数，如果符合条件就试探着再添加一个元素，直到10个找满为止。
我觉得应该是属于回溯算法的吧，但是程序运行出错，哪位大神能解答帮助一下啊，小女子感激不尽
------解决方案--------------------
我是楼主——————————————————
因为一个人不能老是回复，，，
我自己改了一下，现在能运行了，就是如果数据量大的话，运行太慢了。
#include <stdio.h>
FILE *F15, *F500;
int A[1024];
bool checkSum(int count, int x, int *result) //count表示所添加为第几个元素
{
for (int i = 0; i<2^(count-1);i++)
{
int sum = A[i]+x;
for(int j=0; j<2^(count-1); j++)
{
if(sum==A[j])
return false;
}
A[2^(count-1)+i] = sum;
}
result[count-1] = x;
return true;
}
void getSubset(int *arr, int start,int *result,int count,int num,int len,FILE *F)
{
for (int i = start; i >= num-count;)
{
if (count == num) //此时在添加最后一个元素
{
if (checkSum(count,arr[i], result))
{
for (int j = num - 1;j >= 0;j--)
{
fprintf(F,"%d\t",result[j]);
}
fprintf(F,"\n");
}
}
else
{
if (checkSum(count,arr[i], result))
{
getSubset(arr, i-1, result, count+1, num, len, F);
}
getSubset(arr, i-1, result, count, num, len, F);
}
}
}
int main()
{
int a[500], a1[5], a2[10];
for (int i=0; i<100; i++)
a[i] = i+1;
A[0] = 0;
// F15 = fopen("15.xls","w");
F500 = fopen("500.xls","w");
// getSubset(a,15-1,a1,1,5,15,F15);
// fclose(F15);
getSubset(a,500-1,a2,1,10,500,F500);
fclose(F500);
return 0;
}
题目是本来有一个自然数数组，这里是1-500.然后在这个数组里面选取10个数，让这10个数的任意（共2^10次）组合所加的和都不想等。
我的想法就是申请一个全局数列，然后分别从500开始试探添加元素，不符合条件，就换下一个数，如果符合条件就试探着再添加一个元素，直到10个找满为止。
我觉得应该是属于回溯算法的吧，但是程序运行出错，哪位大神能解答帮助一下啊，小女子感激不尽
算法
程序修改
c/c++
------解决方案--------------------
我是楼主——————————————————
因为一个人不能老是回复，，，
我自己改了一下，现在能运行了，就是如果数据量大的话，运行太慢了。
#include <stdio.h>
#include <math.h>
FILE *F15, *F500;
int A[1024];
bool checkSum(int count, int x, int *result) //count表示所添加为第几个元素
{
for (int i = 0; i<pow(2,count-1);i++)
{
int sum = A[i]+x;
for(int j=0; j<pow(2,count-1); j++)
{
if(sum==A[j])
return false;
}
A[int(pow(2,count-1))+i] = sum;
}
result[count-1] = x;
return true;
}
void getSubset(int *arr, int i,int *result,int count,int num,int len,FILE *F)
{
if(i>=num-count)
{
if (count==num) //此时在添加最后一个元素
{
if (checkSum(count,arr[i], result))
{
for (int j = num - 1;j >= 0;j--)
{
fprintf(F,"%d\t",result[j]);
}
fprintf(F,"\n");
}
getSubset(arr, i-1, result, count, num, len, F);
}
else
{
if (checkSum(count,arr[i], result))
{
getSubset(arr, i-1, result, count+1, num, len, F);
}
getSubset(arr, i-1, result, count, num, len, F);
}