问题的链接如下: https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ 对于任何输入案例,我都没有看到重叠的子问题属性在问题中得到满足。例如,在以下链接中,递归树没有任何重叠的子问题 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;
}
以这种方式思考:
如果set []中的总和等于sum,则有2种不同的可能性:
声明中的OR:return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum);
以递归方式检查可能性1.和2.
如果set []中有一些元素等于求和,则某些点的递归将达到sum = 0的情况;并且它将在最终递归级别返回true,这会将TRUE传播到原始调用(请记住:如果A或B中至少有一个为TRUE,则OR OR B返回TRUE)。
否则,您将达到不等于0且n等于0的情况,它将传播为FALSE。