パーティション問題の再帰関数

Question

問題は、配列内の数値のサブセットが特定のターゲット番号に加算される回数を見つけることです。

例えば、残りの要素は5まで追加するように設定され{1, 3, 4, 5}を分割するには、2つの方法があります：

• は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

他にも述べたように、これはサブセット合計問題（NP完全）です。つまり、問題を解決するために指数関数的なアルゴリズムが必要です。
あなたの関数を見るだけで、をlen-1で1回呼び出した後に、という長さの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; 
} 

これは可能なすべてのサブセットを作成する以前のソリューションであり、ターゲットに一致するものがカウントされます。あなたがC++を使っているので

#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

、あなたはまた、ストアに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)と同じエラーが表示されます。ターゲットを超えていない限り、左から要素を集計します。そのため、これらの要素の一部のみを含むソリューションを見つけることはできません。あなたはアルゴリズムを再考する必要があります。