錯誤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）

回答

相關問題