子集和实施

-1

我实现的子集和算法：子集和实施

SUBSET SUM(X[1 .. n], T): 
if T = 0 
return T RUE 
else if T < 0 or n = 0 
return FALSE 
else 
return SUBSET SUM(X[2 .. n], T) ∨ SUBSET SUM(X[2 .. n], T − X[1])

请帮我在哪能通过减少阵列X [2 ... N]递归时？

这是我写的代码，它会导致段故障：

#include <stdio.h> 

    int subsetsum(int a[], int sum, int size) 
    { 
      if(sum==0) 
      return 1; 
      else if (sum<0 || size <0) 
      return 0; 
      else 
      return (subsetsum(a+1 , sum, size-1) || subsetsum(a+1, sum - *a, size-1)); 
    } 
    ` 

    int main(int argc, char **argv) 
    { 
      int a[]={2,4,1,3,5},x; 
      x=subsetsum(a,6,5); 
      printf("%d",x); 
      return 0; 
    }

来源

2012-06-28 hashinclude

请出示你至今创作并哪儿是你坚持的代码。 – jrok

以下是代码： http://pastebin.com/mxg97e4x 给出分段错误。 – hashinclude

C或C++。选择。决定。繁荣。 – rubenvb

Array的在C/C作为函数的参数使用时++被隐式衰变成指针到原来的存储器缓冲器表示该数组。所以为了通过X[2...n]，你只需要将数组指针参数递增1即可。举例来说，你可以做类似如下：

bool subset_sum(const int* array, const int array_size, int* sum) 
{ 
    //...your code for the rest of the algorithm 

    subset_sum(array+1, array_size, sum) //one of the recursive calls 
}

传递参数array+1上的下一个递归调用将由一个递增数组指针，并采取指向数组的指针X[1...n]，现在使它指向数组X[2...n]。您将使用array_size参数来检测数组的结尾。

最后，你会打电话subset_sum像这样：

int array_numbers = {1, 2, 3, 4, 5, 6, 7}; 
int sum = 0; 

subset_sum(array_numbers, sizeof(array_numbers)/sizeof(int), &sum);

来源

2012-06-28 12:33:06 Jason

我写了这段代码： - http://pastebin.com/mxg97e4x 给出了分段错误。 – hashinclude

将else else（sum <0 || size <0）'改为else else（sum <0 || size == 0） – Jason

ok。谢谢。我的代码现在正在工作。这里是： - http://pastebin.com/hevSX8mr – hashinclude

template<class It> 
void recurse(It begin, It end) 
{ 
    ... recurse(begin+1, end) ... 
}

来源

2012-06-28 12:35:55

回答

相关问题