理解子集總和

我剛剛在大學開始學習Backtracking算法。不知何故，我設法爲Subset-Sum問題製作程序。工作正常，但後來我發現我的程序並沒有給出所有可能的組合。理解子集總和

例如：目標總數可能有一百個組合，但我的程序只給出30. 這裏是代碼。如果有人能指出我的錯誤是什麼，這將是一個很大的幫助。

int tot=0;//tot is the total sum of all the numbers in the set. 
int prob[500], d, s[100], top = -1, n; // n = number of elements in the set. prob[i] is the array with the set. 
void subset() 
{ 
    int i=0,sum=0; //sum - being updated at every iteration and check if it matches 'd' 
    while(i<n) 
    { 
     if((sum+prob[i] <= d)&&(prob[i] <= d)) 
     { 
      s[++top] = i; 
      sum+=prob[i]; 
     } 
     if(sum == d) // d is the target sum 
     { 
      show(); // this function just displays the integer array 's' 
      top = -1; // top points to the recent number added to the int array 's' 
      i = s[top+1]; 
      sum = 0; 
     } 
     i++; 
     while(i == n && top!=-1) 
     { 
      sum-=prob[s[top]]; 
      i = s[top--]+1; 
     } 
    } 
} 

int main() 
{ 
    cout<<"Enter number of elements : ";cin>>n; 
    cout<<"Enter required sum : ";cin>>d; 
    cout<<"Enter SET :\n"; 
    for(int i=0;i<n;i++) 
    { 
     cin>>prob[i]; 
     tot+=prob[i]; 
    } 
    if(d <= tot) 
    { 
     subset(); 
    } 
    return 0; 
}

當我運行程序：

Enter number of elements : 7 
Enter the required sum : 12 
Enter SET : 
4 3 2 6 8 12 21 

SOLUTION 1 : 4, 2, 6 
SOLUTION 2 : 12

雖然4,8也是一個解決方案，我的程序犯規表現出來。其輸入數量爲100或更多時更爲糟糕。將有ATLEAST 10000種組合，但我的程序顯示了100

我正努力遵循的邏輯：在主集合中的元素

考慮到的一個子集，只要總和該子集保持小於或等於目標總和。
如果在子集合中增加一個特定的數字使得它大於目標，它就不會考慮它。
一旦達到設定的結束和答案還沒有找到，它會從一組最最近拍攝的數字，並開始尋找在除去最近數的位置後的位置的數字。（因爲我存儲在數組''是主要SET中選定數字的位置）。

來源

2013-03-29 thekeystroker

如果你的變量有更多的描述性名字（這對你的編程生涯總的來說很有用），或者至少如果你告訴我們每一個應該是什麼意思，它們是如何聲明，初始化等的 – Angew

您可以添加一些示例輸入，您希望輸出的內容以及輸出是什麼。這個代碼如何給出任何東西，或者從哪裏得到輸入，都不是很清楚。 – john

對不起，太模糊了。這是我第一次在網上發佈代碼。 – thekeystroker

你會發現依賴於集中的條目順序上的解決方案，因爲在步驟1中

如果你把條目，只要他們不」你的「只要」條款不要讓你過目標，一旦你拿到了，例如'4'和'2'，'8'將帶你超過目標，所以只要'8'之前的'2'在你的設置中，你將永遠不會得到'4'和'8'的子集。

您應該添加跳過添加條目（或將其添加到一個子集但不添加到另一個子集）的可能性或更改您的集合的順序並重新檢查它。

來源

2013-03-31 12:47:10 rlc

這幾乎是正確的 - 如果實際上沒有解決方案可以從4和2構建，那麼內部'while'循環將擺脫2並開始搜索它的右側。 –

@j_random_hacker問題是，如果一個解決方案可以用4和2構建，它應該仍然嘗試沒有2，找到與4沒有2的組合。 – rlc

這是正確的，但是你的答案略有不同。「只要'8'之前的'2'在你的設置中，你永遠不會得到一個'4'和'8'不成立的子集 - 如果存在的話，你可以得到一個子集4和8沒有辦法用4和2做出解決方案。 –

這可能是一個免費的堆棧解決方案是可行的，但平時（一般最簡單的！）的方式來實現回溯算法是通過遞歸，如：

int i = 0, n; // i needs to be visible to show() 
int s[100]; 

// Considering only the subset of prob[] values whose indexes are >= start, 
// print all subsets that sum to total. 
void new_subsets(int start, int total) { 
    if (total == 0) show(); // total == 0 means we already have a solution 

    // Look for the next number that could fit 
    while (start < n && prob[start] > total) { 
     ++start; 
    } 

    if (start < n) { 
     // We found a number, prob[start], that can be added without overflow. 
     // Try including it by solving the subproblem that results. 
     s[i++] = start; 
     new_subsets(start + 1, total - prob[start]); 
     i--; 

     // Now try excluding it by solving the subproblem that results. 
     new_subsets(start + 1, total); 
    } 
}

你可以這樣從main()調用此與new_subsets(0, d);。首先，遞歸的理解起來可能會非常棘手，但重要的是要讓自己的頭腦清楚 - 嘗試更簡單的問題（例如遞歸地生成斐波納契數字），如果上述內容沒有任何意義。

與您提供的解決方案一起工作，我可以看到的一個問題是，只要找到解決方案，就會將其清除並開始尋找從第一個數字右邊的數字開始尋找新解決方案被包括在該解決方案中（top = -1; i = s[top+1];意味着i = s[0]，並且隨後有i++;）。這會錯過以相同的第一個數字開頭的解決方案。您應該只做if (sum == d) { show(); }，以確保您獲得全部。

我最初發現你內心的while循環相當混亂，但我認爲它實際上是在做正確的事：曾經i打數組的結尾，它會刪除添加到部分解決方案的最後一個號碼，如果這個號碼是數組中的最後一個數字，它將再次循環以從部分解決方案中刪除倒數第二個數字。它不能循環兩次以上，因爲包含在部分解決方案中的數字都處於不同的位置。

來源

2013-03-31 14:38:02

我還沒有詳細分析算法，但是令我感到震驚的是，您的算法沒有考慮到在有一個以數字X開頭的解決方案之後，可能會有多個解決方案以該數字開始。

第一個改進是避免重置您的堆棧s和打印解決方案後的運行總和。

來源

2013-03-31 15:01:00

理解子集總和

回答

相關問題