Подзадачи суммы перекрывающихся подзадач (динамическое программирование)

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

c++ dynamic-programming subset-sum
person Neha Sharma    schedule 31.12.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Если сумма в элементах set [] равна сумме, возможны 2 различных варианта:

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

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

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

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

В противном случае вы достигнете суммы наблюдений, не равной 0, а n равно 0, что приведет к распространению FALSE.

person StPiere    schedule 31.12.2017
comment
Спасибо, но я уже разбираюсь в коде. Я не понимаю свойство перекрывающихся подзадач для этого вопроса - person Neha Sharma; 31.12.2017