动态规划失败的测试情况下

Question

问题定义：

计数一组归纳到值10一旦确定一个对中的最长子集对，这些2个号码不能用于形成其他对。输出应该是一个数字，表示这些对中涉及的数字的数量。

输入：1 {1,2,8,9,1,9,1,9}答案：6（3对，6个数字，索引= {0,7}，{3,6}，{4 ，5}）

输入：2 {5,5,5,5,5,5,5,5}答案：8（4对，8个数字，索引= {0,7}，{1,6 }，{2,5}，{3,4}）

输入：3 {2,4,3,7,3,8,6,7}答案：4（2对，4个数字，索引= {0,5}，{3,4}或{0,5}，{2,3}或{2,7}，{3,4}或{1,6}，{2,3}或{1 ，6}，

我已经写下面的代码{3,4}）：

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

#define ARRAYSIZE 10 
#define SUM 10 

int d[ARRAYSIZE][ARRAYSIZE]; 
int count = 0; 
int final[ARRAYSIZE/2]; 
int reset = 0; 
int subset_to_sum(int a[], int m, int n, int sum) 
{ 
    //printf("%d %d %d \t",m,n,d[m][n]); 
    if (m >= n) 
     return 0; 
    if (d[m][n] != -1) 
     return d[m][n]; 

    if (a[m]+a[n] == sum) 
    { 
     d[m][n] = 1; 
     count = count+1; 
     //printf("%d\n",count); 
     if (m+1>=n-1) 
     { 
      final[reset] = count; 
      reset = reset+1; 
      count = 0; 
     } 
     else 
      final[reset] = count; 
     return 1+subset_to_sum(a, m+1, n-1, sum); 
    } 
    else if (a[m] > sum) 
     return subset_to_sum(a, m+1, n, sum); 
    else if(a[n] > sum) 
     return subset_to_sum(a, m, n-1, sum); 
    else 
     return (subset_to_sum(a, m+1, n, sum)+subset_to_sum(a, m, n-1, sum)+subset_to_sum(a, m+1, n-1, sum));  
} 

int main(void) 
{ 
    int i = 0; 
    int j; 
    int inc; 

    //int set[] = {1,2,8,9,1,9,1,9}; 
    //int set[] = {1,2,8,4,5,9,1,9}; 
    //int set[] = {2,4,3,7,3,8,6,7}; 
    //int set[] = {5,5,5,5,5,5,5,5}; 
    //int set[] = {25,35,45,5,6,7,8,9}; 
    //int set[] = {1,2,3,4,5,6,7,8,9,10}; 

    for(i=0;i<ARRAYSIZE;i++) 
    { 
     for(j=0;j<ARRAYSIZE;j++) 
     { 
      d[i][j] = -1; 
     } 
    } 
      printf("\n"); 
    //printf("Total Pairs making sum %d is : %d\n",SUM,subset_to_sum(set, 0, ARRAYSIZE-1, SUM)*2); 
    subset_to_sum(set, 0, ARRAYSIZE-1, SUM); 

    int max = 0; 
    for(i=0;i<4;i++) 
    { 
     if(final[i]>max) 
      max = final[i]; 
    } 
    printf("Subset Pairs making sum %d is: %d\n",SUM,max*2); 
    return 0; 
} 

我的代码输入失败：{1,2,3,4,5,6,7,8,9,10}。有人能指出我的方法存在缺陷吗？

谢谢！

Answer 1

我修改你的代码一点点，你可以请尝试以下：

int subset_to_sum(int a[], int m, int n, int sum) 
{ 

if (m >= n) 
    return 0; 

if (a[m]+a[n] == sum) 
    return 1+subset_to_sum(a, m+1, n, sum) + subset_to_sum(a, m, n-1, sum); 
else 
    return subset_to_sum(a, m+1, n, sum) + subset_to_sum(a, m, n-1, sum);  
}