質問へのリンクは次のとおりです。
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;
}
ありがとうございますが、私はすでにコードを理解しています。私はこの質問のために重複するサブ問題の性質を理解してはいけません –