2017-12-31 18 views
0

質問へのリンクは次のとおりです。
https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
私が今まで入力する場合のために、少なくとも質問に成就された重複部分問題のプロパティが表示されません。 follwingリンクで例えば 、再帰的なツリーはまた、例えば以下のプログラムで重複する部分問題がない
http://www.zrzahid.com/subset-sum-problem-dynamic-programming/
サブセット合計重複する部分問題(ダイナミックプログラミング)

任意の重複部分問題を持っていません。サブプログラムの重複がない場合、ダイナミックプログラミングがどのように役立つのか分かりません。説明してください。

bool isSubsetSum(int set[],int n, int sum) 
{ 
    if(sum==0) 
return true; 
if(n==0 || sum<0) 
    return false; 
return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum); 
} 
int main() 
{ 
    int set[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = sizeof(set)/sizeof(set[0]); 
    if (isSubsetSum(set, n, sum) == true) 
    printf("Found a subset with given sum"); 
    else 
    printf("No subset with given sum"); 
    return 0; 
} 

答えて

0

それについてこのように考える:集合[]の要素内の和がある場合

は、2つの異なる可能性がある和に等しい:

  1. 最後の要素(そのインデックスはn-1である)は、 の合計に含まれ、その場合、他のn-1個の要素は合計での合計である - [n-1]

  2. 最後の要素(そのインデックスはn-1)は、 ->に含まれません。その場合、他のn-1要素は合計での合計になります。

ステートメントのOR:return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum);は、可能性1.と2.の両方を再帰的にチェックします。

場合 = 0に到達するある時点で再帰にセット[]に等しいにおけるいくつかの要素が存在する場合、最下位の再帰レベルでtrueを返します。TRUEを元の呼び出しまで伝播します(AまたはBの少なくとも1つがTRUEの場合、A OR BはTRUEを返します)。

そうでない場合は、0に等しくないケースの合計に達しており、nは0に等しいです。これが偽を伝播します。

+0

ありがとうございますが、私はすでにコードを理解しています。私はこの質問のために重複するサブ問題の性質を理解してはいけません –