Рекурсия: Понимание (подмножество) схемы включения / исключения

Question

Рекурсия: Понимание (подмножество) схемы включения / исключения

Мне нужно понять, как работает эта рекурсия, я понимаю простые рекурсивные примеры, но сложнее более сложные. Даже думал, что есть только две строки кода, с которыми у меня возникли проблемы … return Само заявление. Я просто рисую пробел о том, как это работает, особенно оператор и / или оператор. Любое понимание очень приветствуется.

      bool subsetSumExists(Set<int> & set, int target) {
if (set.isEmpty()) {
return target == 0;
} else {
int element = set.first();
Set<int> rest = set - element;
return subsetSumExists(rest, target)
|| subsetSumExists(rest, target - element);
}
}

0

c++recursion subset-sum

Решение

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

Рекурсивный код обычно связан с понятием редукции. В общем, сокращение — это средство для сведения неизвестной проблемы к известной посредством некоторого преобразования.

Давайте посмотрим на ваш код. Вам необходимо выяснить, может ли данная целевая сумма быть построена из элементов набора входных данных.
Если набор данных пуст, делать нечего, кроме сравнения целевой суммы с 0.

В противном случае, давайте применим сокращение. Если мы выбираем число из набора, на самом деле может быть 2 варианта — выбранный номер участвует в сумме, которую вы ищете, или нет. Других возможностей здесь нет (очень важно охватить весь спектр возможностей!). На самом деле, не имеет значения, какой элемент данных выбран, если вы можете охватить все возможности для оставшихся данных.

Первый случай: номер не участвует в сумме. Мы можем уменьшить проблему до меньшего, с набором данных без проверяемого элемента и той же целевой суммой.

Второй случай: число участвует в сумме. Мы можем уменьшить проблему до меньшего, с набором данных без проверяемого элемента и запрошенной суммой, уменьшенной на значение числа.

Обратите внимание, что на данный момент вы не знаете, является ли любой из этих случаев истинным. Вы просто продолжаете уменьшать их, пока не доберетесь до тривиального пустого кейса, где сможете точно знать ответ.

Ответ на первоначальный вопрос будет верным, если он верен для любого из этих двух случаев. Это именно то, что оператор || делает — он выдаст истину, если любой из его операндов (результат двух случаев) верен.

5

|| это логическое ИЛИ. Он оценивается слева направо и короткозамкнут.

Это означает, что в выражении A || B, A оценивается первым. Если это true, все выражение true и дальнейшая оценка не проводится. Если A является false, B оценивается, и выражение получает значение B,

В вашем примере A это «попробуйте получить ту же сумму, не используя 1-й элемент из набора». B это «использовать 1-й элемент из набора, который уменьшает общую сумму, оставшуюся до суммы, и попытаться получить это с остальной частью элемента».

3

Давайте сначала посмотрим на алгоритм ..

Базовый случай (т. Е. Случай, когда рекурсия завершается) — это когда набор пуст.
В противном случае программа берет первые элементы, вычитает их из набора.
Теперь позвоню subsetSumExists(rest, target) и проверить, если это правда,
если он вернет true, иначе он вызовет
subsetSumExists(rest, target - element) и вернуть что бы то ни было
возвращается.

Проще говоря, это будет называть subsetSumExists(rest, target - element) только если первый subsetSumExists(rest, target) возвращает ложь

Теперь давайте попробуем выполнить этот код всухую с небольшим набором примеров {3,5} и суммой 8. Теперь я буду вызывать функцию sSE

sSE({3,5}, 8) => "sSE({5}, 8) || sSE({5},(8-3))"
sSE({5}, 8)   => sSE({}, 8) || sSE({}, (8-5))

sSE({}, 8)    => false.. now will call sSE({}, (8-5))

sSE({}, 3)    => false.. now will call sSE({5}, (8-3))

sSE({5}, 5)   => sSE({}, 5} || sSE({}, (5-5))

sSE({}, 5)    => false.. now will call sSE({}, (5-5))

sSE({}, 0)    => true.. ends here and return true

2

Вычитание набора выглядит странным синтаксисом, но я предполагаю, что это означает pop () для элемента.

Он «работает» путем нахождения каждой возможной комбинации, хотя и является экспоненциальным.

в || В данном случае LHS — это сумма, включающая текущий элемент, а RHS — это сумма, исключающая его. Таким образом, вы получите по экспоненциальному дереву каждую комбинацию каждого элемента, либо включенную, либо выключенную.

Между прочим, экспоненциальный означает, что если у вас есть 30 элементов, это даст 2 в степени 30, т.е. 0x40000000 или около миллиарда комбинаций.

Конечно, у вас может не хватить памяти.

Если он найдет решение, он может пройти не все 2 ^ N случаев. Если нет решения, оно всегда посетит их всех.

1

Если я говорю за себя, трудности в понимании проблемы проистекают из || оператор. Давайте посмотрим на нижнюю инструкцию возврата того же кода другим способом,

if (subsetSumExists(rest, target - element))
return true;
if (subsetSumExists(rest, target))
return true;

return false;

0

Источник

Accepted Answer

Чтобы понять рекурсию, нужно понимать рекурсию.
Чтобы сделать это, вы должны думать рекурсивно.

В этом конкретном случае.

Для любого: subsetSum(set, target)

Если set пусто И target 0, то subsetSum существует
В противном случае удалите первый элемент set, проверить, если subdetSum(set, target) существует ИЛИ subdetSum(set, target - removed_element) существует (используя шаг 0)

1