Subset Sum Overlapping subproblems (Динамическое программирование)

Ссылка на вопрос следующая:
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;
}

0

Решение

Подумайте об этом таким образом:

Если в set [] есть сумма, равная сумма Есть 2 возможности:

  1. последний элемент (его индекс n-1) входит в сумму
    -> в этом случае остальные n-1 элементов суммируют до сумма — установить [п-1]

  2. последний элемент (его индекс n-1) не входит в сумму
    -> в этом случае остальные n-1 элементов суммируют до сумма.

ИЛИ в заявлении: return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum); проверяет обе возможности 1. и 2. рекурсивно.

Если в set [] есть несколько элементов, равных сумма рекурсия в какой-то момент дойдет до случая сумма = 0; и он вернет истину на самом низком уровне рекурсии, который распространит значение ИСТИНА до исходного вызова (помните: А ИЛИ Б возвращает ИСТИНА, если хотя бы один из А или В равен ИСТИНА).

В противном случае вы достигнете суммы регистра, не равной 0, а n равно 0, что будет распространяться как ЛОЖЬ.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]