Уменьшение времени выполнения для моей рекурсивной суммы подмножества algorthim

У меня есть рекурсивный алгоритм DFS, который правильно подсчитывает количество имеющихся подмножеств. Однако время выполнения этого метода абсурдно и чрезвычайно экспоненциально. Например, когда arr содержит набор ниже. Сумма, которую мы ищем, равна 50. В arr удалены все дубликаты и числа, большие или равные 50. Затем массив сортируется.

21 3 42 10 13 17 33 26 19 7 11 30 24 2 5

arr содержит список слов в отсортированном порядке

k - начальный размер массива

sum - это сумма, которую мы ищем в подмножествах, в этом примере это 50

 public static void recDfs(ArrayList<Integer> arr, int k, int sum) {
    if (sum == 0) {
        counter++;
        return;
    }
    if (sum != 0 && k == 0) {
        return;
    }

    recDfs(arr, k - 1, sum - arr.get(k - 1));
    recDfs(arr, k - 1, sum);
}

Это очень быстро даст правильный результат, который размещен ниже.

Истекшее время: = 0,004838 Существует 51 количество подмножеств, которые в сумме составляют 50 УСПЕШНЫХ СТРОИТЬ (общее время: 0 секунд)

Однако этот алгоритм увеличивается экспоненциально, когда у нас есть новый набор в массиве, например.

99 49 1 7 23 83 72 6 202 78 26 79 351 34 107 76 38 50 32 62 71 9 101 77 81 92 89 66 97 57 33 75 68 93 100 28 42 59 29 14 122 24 60 2 37 192 73 84 31 4 87 65 19

Когда мы снова вызываем recDfs с новым массивом, который также сортируется и удаляются дубликаты с суммой 107, время выполнения абсурдно, однако печатается правильное количество подмножеств.

Истекшее время: = 19853,771050 Имеется 1845 подмножеств, которые в сумме составляют 107 УСПЕШНО СОЗДАТЬ (общее время: 330 минут 54 секунды)

Я ищу более эффективные способы реализации этого алгоритма.


java recursion algorithm big-o subset-sum
person user3328187    schedule 03.03.2015    source источник
comment
Подсказки: динамическое программирование, мемоизация;)   -  person Shashank    schedule 03.03.2015
comment
en.wikipedia.org/wiki/Subset_sum_problem   -  person Florent Bayle    schedule 03.03.2015
comment
Это также можно сделать с помощью табуляции, но код будет выглядеть иначе, поскольку вы будете двигаться снизу вверх, а не сверху вниз. Тем не менее, это хорошее упражнение в DP.   -  person Shashank    schedule 03.03.2015

Ответы (1)


arrow_upward
4
arrow_downward

Некоторые незначительные оптимизации, если я правильно понимаю:

 public static void recDfs(int[] arr, int k, int sum) {
    if (sum < 0) return;

    if (sum == 0) {
        counter++;
        return;
    }
    if (k == 0) {
        return;
    }

    recDfs(arr, k - 1, sum - arr[k - 1]);
    recDfs(arr, k - 1, sum);
}

Если я правильно интерпретирую, вы можете оставить ветку залогом, если сумма меньше 0, что может сэкономить много времени. (Невозможно сделать, если есть отрицательные числа) Другая небольшая оптимизация заключается в использовании массива int. Это должно сэкономить немного времени по сравнению с использованием ArrayList из целых чисел. Если вы хотите пофантазировать, вы можете использовать несколько потоков.

person Necreaux    schedule 03.03.2015