分區問題的遞歸函數

Question

問題是要找出數組中某個子集的數量合計到特定目標數量的次數。

例如，有兩種方式，使剩餘的元素加起來5集合進行分區{1, 3, 4, 5}：

• 選擇1和4
• 只選擇5

相比之下，沒有辦法劃分集{1, 3, 4, 5}得到11.

#include "genlib.h" 
#include <iostream> 

void RecursePart(int[], int, int, int&); 
int Wrapper(int[], int, int); 


int main() { 
    int arr[8] = {1,2,3,4,5,6,7,8}; 
    cout << Wrapper(arr, 8, 11); 
} 


void RecursePart(int arr[], int len, int target, int& ctr) { 
    if (len == 1) { 
     if (arr[0] == target) { 
      ctr++; 
     } 
     return; 
    } 

    int sum, temp; 
    sum = temp = arr[0]; 

    for (int j = 1; j < len; j++) { 
     if (sum == target) { 
      ctr++; 
      break; 
     } 

     sum = sum + arr[j]; 

     if (sum == target) { 
      ctr++; 
      sum = temp; 
      continue;   
     } 

     if (sum > target) { 
      sum = temp; 
      continue; 
     } 

     if (sum < target) { 
      temp = sum; 
      continue; 
     }  
    } 

    RecursePart(arr + 1, len - 1, target, ctr); 
} 

int Wrapper(int arr[], int len, int target) { 
    int n = 0; 
    RecursePart(arr, len, target, n); 
    return n; 
} 

問題是，我得到的輸出是1，但數組中的數字的一個子集加起來大於11的次數大於1.我試圖追蹤算法，我知道問題必須在for循環中。在那裏算法跳過一些總和。我怎麼能覆蓋這個問題？

Answer 1

與其他人一樣，這是Subset Sum問題（這是NP完全問題），這意味着您需要一個指數時間算法來解決它。
僅僅通過查看你的函數，你可以每次使用len-1調用RecursePart一次，然後得到一個長度爲n的for-loop，這意味着你的計算是O(n^2)。這顯然不會解決O(2^n)問題。

以下是創建子集總和的遞歸解決方案，並嘗試查看它們是否到達目標。如果當前子集沒有等於目標的選項，則停止當前子集的「創建」。

int RecursePart(int arr[], int len, int idx, int curr_sum, int target)  
{   
    int count = 0; 

    // this subset is good 
    if (curr_sum == target) 
     return 1; 

    // the sum of the current subset exceeds target, no point in continuing 
    if (curr_sum > target || idx == len) 
     return 0; 

    count += RecursePart(arr, len, idx+1, curr_sum + arr[idx], target); 
    count += RecursePart(arr, len, idx+1, curr_sum, target); 

    return count; 
} 

這是我以前的解決方案，它創建所有可能的子集，並且匹配目標的子集被計數。

#include <iostream> 

int Wrapper(int[], int, int); 

int main() { 
    int arr[8] = {1,2,3,4,5,6,7,8}; 
    std::cout << Wrapper(arr, 8, 11); 
} 

// counts the sum of a subset 
int CountSet(int* arr, int* mask, int len) 
{ 
    int sum = 0; 

    for (int i=0; i < len; ++i) 
    { 
     if (mask[i]) 
     { 
      sum += arr[i]; 
     } 
    } 
    return sum; 
} 


int RecursePart(int arr[], int idx, int len, int* subset_mask, int target) 
{ 
    int count = 0; 

    if (idx == len) 
    { 
     if (CountSet(arr, subset_mask, len) == target) 
      return 1; 
     else 
      return 0; 
    } 

    // create the subset "without" me 
    subset_mask[idx] = 0; 
    count += RecursePart(arr, idx+1, len, subset_mask, target); 

    // now create the subset "with" me 
    subset_mask[idx] = 1; 
    count += RecursePart(arr, idx+1, len, subset_mask, target); 

    return count; 
} 

int Wrapper(int arr[], int len, int target) { 

    int* subset_mask = (int*)malloc(len*sizeof(int)); 
    int res = RecursePart(arr, 0, len, subset_mask, target); 
    free(subset_mask); 
    return res; 
} 

Answer 2

由於您使用C++，你一個也使用vector<int>存儲是像這樣的中間解決方案：

#include <iostream> 
#include <vector> 

using namespace std; 

vector<int> RecursePart(int[], int, int, int&); 
int Wrapper(int[], int, int); 


int main() { 
    int arr[8] = {8,2,3,4,5,6,7,1}; 
    cout << Wrapper(arr, 8, 11); 
} 


vector<int> RecursePart(int arr[], int len, int target, int& ctr) 
{ 
    vector<int> return_vec; 

    if (len == 1) 
    { 
     if (arr[0] == target) 
     { 
      ctr++; 
      return return_vec; 
     } 

     return_vec.push_back(arr[0]); 
     return return_vec; 
    } 

    int current = arr[0]; 

    if (current == target) 
     ctr++; 

    if (current < target) 
     return_vec.push_back(current); 

    vector<int> temp; 

    temp = RecursePart(arr + 1, len - 1, target, ctr); 

    for (int i = 0; i < temp.size(); i ++) 
    { 
     if (temp[i] + current == target) 
     { 
      ctr++; 
     } 

     if (temp[i] + current < target) 
      return_vec.push_back(temp[i] + current); 

     if (temp[i] < target) 
      return_vec.push_back(temp[i]); 
    } 

    /*Debug Print 
    cout << "Current: " << current << endl; 
    for (int i = 0 ; i < return_vec.size(); i++) 
    { 
     cout << return_vec[i] << ", "; 
    } 
    cout << endl; 
    */ 

    return return_vec; 
} 

int Wrapper(int arr[], int len, int target) { 
    int n = 0; 
    RecursePart(arr, len, target, n); 
    return n; 
} 

更詳細地說明，所發生的事情是，我們正在使用遞歸分解列出它的最簡單的部分，它是一個單一的數字（列表的最後一個元素），並使我們的返回類型的所有可能的總和小於我們的目標。在基本情況下，它基本上是數組的最後一個元素，如果該數字等於目標，我們增加計數器，並返回一個空向量，因爲返回向量，這是所有可能的總和小於我們的目標，不應該有一個元素等於或大於我們的目標。在前面所有基本情況下的遞歸步驟中，我們得到返回的向量，然後將當前值與返回向量中的所有元素進行比較，再次表示所有可能的總和小於目標。我們檢查是否有任何符合目標的總和，然後將任何總和複製到我們的返回向量中，該向量小於目標。然後我們回到之前的遞歸步驟。

該算法的複雜性仍然是指數...如果啓用debug print部分，您將看到每個迭代的向量長度的增長將如何以指數方式增長，因此對於給定集的大小爲N，您將不得不檢查的解決方案數量將與O（2^N）一致。儘管這個版本的解決方案通過確保我們僅將有效的解決方案移動到下一次迭代中，但卻使其稍微回退一些，從而避免了計算每個可能的子集的需要。

Answer 3

你的功能簡直是錯誤的。你可以看到與Wrapper(arr,4,5)相同的錯誤。只要不超過目標，就總結左邊的元素，以便找到只涉及其中一些元素的解決方案。您必須重新考慮算法。