错误Subset sum in O（n^2）

我知道这个代码/逻辑对于解决子集和问题是错误的，但似乎无法理解为什么。错误Subset sum in O（n^2）

计算所有可能的子集的总和，并检查是否有任何等于所需的总和。这将在O（n^2）中完成，这显然是错误的，因为我可以通过DP O（n * sum）解决这个问题。

谢谢。

int main() { 
    long long int t,n,i,j; 
    scanf("%lld",&t); 
    while(t--) 
    { 
     long long int p[1005][1005],s[1005][1005]={0}; 
     long long int a[1005],sum; 
     long long int counter=0; 
     scanf("%lld %lld",&n,&sum); 
     for(i=0;i<n;i++) 
      scanf("%lld",&a[i]); 
     s[0][0]=a[0]; 
     for(i=0;i<n;i++) 
     { 
      for(j=i;j<n;j++) 
      { 
       if(i==j) 
       { 
        s[i][j]=a[i]; 
       } 
       else 
       { 
        s[i][j]=a[j]+s[i][j-1]; 
       } 
      } 
     } 
     int flag=0; 
     for(i=0;i<n;i++) 
     { 
      for(j=i;j<n;j++) 
      { 
       if(s[i][j]==sum) 
        flag++; 
      } 
     } 
     if(flag) 
      cout<<1<<endl; 
     else 
      cout<<0<<endl; 

    } 
    return 0; 
}

来源

2015-12-21 someone1

代码在哪里？ – AndyG

另外，子集和是NP完成的。如果你能以比所有问题实例的指数时间更快的速度解决问题，那么你将赢得各种奖品。 – AndyG

我知道这是错误的，我只是要求逻辑上的缺陷。 – someone1

你的代码的问题很简单，你不计算所有子集的总和。这就是为什么你的代码看起来比实际需要的更快。

见https://en.wikipedia.org/wiki/Subset_sum_problem

来源

2015-12-21 19:07:44 4386427

谢谢！一个可能的测试案例，这会失败，所以我可以更好地理解？ – someone1

@ someone1 - 有2^N个子集 - 您只计算N^2个子集。例如：假设N = 20。你在哪里计算由元素编号2,3,5,7,11,13,17和19组成的子集的总和？你没有。 – 4386427

啊！非常感谢。我刚刚意识到我已经解决了这个问题，所以我只计算了连续的子集！非常感谢你，一个非常愚蠢的问题，我本来应该多试一试。抱歉，添麻烦了。 – someone1

问题是s[i][j]只是记录a[i]+a[i+1]+...+a[j]。实际上，您需要记录a[i...j]的所有子集的总和，这应该是2^(j-i)。如果您的目标总和不是连续子集的总和，那么您的代码应该很容易失败。

来源

2015-12-21 19:19:49

错误Subset sum in O（n^2）

回答

相关问题