Поиск суммы подмножества рекурсивно дает неверный результат

Выполнял этот метод (pdf) для реализации рекурсивного решения, но я думаю, что это глючит. Я в точности реализовал это, как описано в файле pdf.

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

Помещение binary[i] = 1 в состояние else if устраняет проблему, но не имеет смысла.

Можно ли уточнить, какое решение правильное?

#define SIZE(a) sizeof(a)/sizeof(a[0])
int binary[100];
void foo(int target, int i, int sum, int *a, int size) {
    binary[i] = 1;
    if (target == sum+a[i]) {
        int j;
        for (j=0;j<size;j++)
            printf("%d\n", binary[j]);
        return;
    } else if ((i+1 < size) && (sum + a[i] < target)) {
        foo(target, i+1, sum + a[i], a, size);
    }
    if ((i+1 < size) && (sum +a[i+1] <= target)) {
        binary[i] = 0;
        foo(target, i+1, sum, a, size);
    }
}

int main()
{
    int i, target =10,a[] = {1, 2, 3, 5, 100};
    foo(target, 0, 0, a, SIZE(a));
}

Токовый выход: 0 1 1 1 1

Ожидаемый результат: 0 1 1 1 0


c recursion algorithm subset-sum
person newbie_old    schedule 27.06.2015    source источник
comment
какой язык? C? C ++? пожалуйста, пометьте соответственно   -  person m.s.    schedule 27.06.2015
comment
Пожалуйста, добавьте текущий вывод, а вместо него правильный вывод, который вы ожидаете. Также постарайтесь упростить себе задачу и не используйте t, i и a, а используйте осмысленные имена переменных.   -  person wimh    schedule 27.06.2015

Ответы (1)


arrow_upward
0
arrow_downward 

#include <stdio.h>

#define SIZE(a) sizeof(a)/sizeof(a[0])
int binary[100];

void show(int* p, int size) {
    int j;
    for (j = 0; j < size; j++)
        printf("%d\n", p[j]);
}

void foo(int target, int i, int sum, int *a, int size) {
    if (sum == target) {
        // solution found
        show(binary, size);
    } else if (sum < target && i < size) {
        // try both branches
        // 1. current value used
        binary[i] = 1;
        foo(target, i + 1, sum + a[i], a, size);
        // 2. current value skipped
        binary[i] = 0;
        foo(target, i + 1, sum, a, size);
    } else {
        // no solution on this path
    }
}

int main() {
    int target = 10;
    int a[] = {1, 2, 3, 5, 100};
    foo(target, 0, 0, a, SIZE(a));
}

Объяснение:

  • Давайте говорить только о i, sum и binary, потому что все остальное с точки зрения этого алгоритма постоянно.
  • Наша цель - выбрать отдельные элементы из a, сумма которых равна target. Когда мы дойдем до этой ситуации, мы закончим, и наша единственная работа - show найти решение.
  • Алгоритм может продолжаться, только если наш текущий sum все еще ниже target, а мы еще не достигли конца a.
  • Всегда есть две возможности: использовать текущий элемент или пропустить его. Оба исследуются рекурсивно.
  • Процедура должна оставлять ноль в соответствующей позиции binary, в противном случае она будет давать вводящие в заблуждение результаты на различных уровнях обратного отслеживания . По этой причине в первую очередь исследуется ветвь use.
person dlask    schedule 27.06.2015
comment
@newbie_old Вы правы. Я исправил свой ответ. Мне пришлось изменить условие i + 1 < size на i < size, а также заменить использованные и пропущенные ветки, чтобы оставить ноль в массиве binary для других решений, которые, возможно, найдены возврат. - person dlask; 28.06.2015