Subset Sum с помощью рекурсивного

Question

моего вклада:

W[10] = {1, 3, 5, 7, 9, 12, 19, 22, 36, 63} 
X[10] = {0}; 
M = 79; 

я назвал функцию:

findSolution(0,0,177); <br> 

Примечание: 177 является суммой всех элементов внутри W массива.

void findSolution(int s, int k, int r) { 
    cout << "fn(" << s << " , " << k << ", " << r << ")" << endl; 
    X[k] = 1; 
    if (s + W[k] == M){ 
     printArr(X); 
    } 
    else if (s + W[k] + W[k + 1] <= M) { 
     return findSolution(s + W[k], k + 1, r - W[k]); 
    } 

    if ((s + r - W[k] >= M) && (s + W[k + 1]) <= M){ 
     X[k] = 0; 
     return findSolution(s, k + 1, r - W[k]); 
    } 
} 

Выход:

fn(0 , 0, 177) 
fn(1 , 1, 176) 
fn(4 , 2, 173) 
fn(9 , 3, 168) 
fn(16 , 4, 161) 
fn(25 , 5, 152) 
fn(37 , 6, 140) 
fn(56 , 7, 121) 

Выходной приведенный выше, чтобы отслеживать вызовы функций. Выход заканчивается здесь и не идет вперед. Что не так с моим кодом. Я пытаюсь напечатать подмножество, которое дает желаемую сумму = 79. Рекурсивный вызов не возвращается.

Answer 1

Рекурсивный звонок is возвращение назад; это просто так, прежде чем вы нашли решение. Это может произойти, если последний if достигнут, но не удался. (Обратите внимание, что то, что выглядит как ваш базовый случай, когда вы звоните printArr, делает не обязательно остановить рекурсию.)

Answer 2

Проблема с вашим решением является то, что он использует стратегию greedy (т.е. не «вернуться назад» после того, как нахождение подходящего кандидата).

Вашего алгоритм проверяет для трех условий:

• Вы нашли решение,
• Решения возможно, если вы добавитьk его элемента подмножества, или
• решения возможно если вы заменитьk-1-элемент с k -й.

Эта стратегия не исчерпывают все возможности: например, он не может быть возможным заменить k -ю элемент с k+1 -st, но это может быть возможным заменить несколько элементов впереди k -го с k+1 - и получить решение. Ваша стратегия жадная, потому что когда обнаруживается, что элемент может быть добавлен в набор (то есть s + W[k] + W[k + 1] <= M), он принимает этот путь и никогда не оглядывается назад (т.е. возвращается из этой ветви).

Вы можете исправить это путем реорганизации коды следующим образом:

• Сделайте свою функцию возврат true при обнаружении решения, и false иначе.
• Сохраните базовый футляр if (s + W[k] == M) и добавьте return true, когда решение найдено.
• Проверьте, есть ли возможность добавить k -й элемент в комплект. Если это возможно, добавьте его и попробуйте для частичной суммы s + W[k]
• Проверьте возврат рекурсивного вызова. Если это true, верните true.
• В противном случае удалите k-й элемент из набора и сделайте второй рекурсивный вызов без k -го элемента в миксе. Используйте ту же частичную сумму s.
• Возвращает значение последнего рекурсивного вызова вызывающему.

Теперь ваш алгоритм является исчерпывающим, поскольку для каждого элемента алгоритм пытается найти частичную сумму и когда элемент является частью решения, а когда элемент не является частью решения (т.е. O (2 ⁿ) проверяет все).