Найти все подмножества множества, сумма до п

Question

Вот код, который я придумал:

static void findNumbers(int[] list, int index, int current, int goal, String result) 
{ 
    if (list.length < index || current>goal) 
      return; 
    for (int i = index; i < list.length; i++) { 
     if (current + list[i] == goal) { 
     System.out.println(result + " " + String.valueOf(list[i])); 
     } 
     else if (current + list[i] < goal) { 
      findNumbers(list, i + 1, current + list[i], goal, result + " " + String.valueOf(list[i])); 
     } 
    } 
} 

Зов это с помощью:

findNumbers(array, starting_index, current_sum_till_now, target_sum, ""); 

Может кто-то помочь мне выяснить время сложность этого кода я считаю его экспоненциальным.

Что является наиболее оптимальным способом решения этой проблемы? Использует ли он обратный путь?

Answer 1

Было указано, что я совершил ошибку. Я умножал сложности рекурсивных вызовов, пока я должен был добавить их. Итак, C(N) = C(N-1) + C(N-2) + .... То же самое применимо к C(N-1), C(N-2) и т. Д. Это означает, что сложность isnt 'O(N!).

Это заставило меня задуматься над алгоритмом с другой точки зрения. Он проверяет каждое возможное подмножество. Так как есть возможных подмножеств (пустое подмножество не учитывается), то сложность O(2^N), что я считаю вашей исходной ставкой.

Answer 2

Как уже указывалось, это хуже, чем N^2, на самом деле это выглядит как O (N!). Вы немного сэкономите, так как вы можете выйти на некоторые из циклов раньше, но степень экономии будет зависеть от того, как быстро устраняются возможности.

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

Answer 3

Вот способ сделать это с помощью динамического программирования и ранцевой аналогии: -

1. сортировки набора в порядке возрастания

2. Оценить подмножество до list[i] <= N

3. Решить котомку за мешок от емкости N и элементов, имеющих значение и вес, как их list[i]

4. Если на конечной емкости ранца N = максимальная прибыль, то по крайней мере существует одно подмножество решения.

5. восстановить все решения для ранца с использованием матрицы затрат и получить все подмножества решений.

Временная сложность:O(|S|*N + K) |S|- length of set and K is number of subsets. Это полиномиальный алгоритм времени псевдо.

Примечание: Проблема, являющаяся NP-hard, алгоритм полиномиального времени еще не обнаружен.

Edit: - Retrace решение от булевой матрицы

void retrace(int n,boolean[] solution,int target) { 

    if(n>=0) { 

     if(table[target][n-1]) { 

      solution[n] = false; 
      retrace(n-1,solution,target); 
     } 

     if(table[target-numbers[n]][n-1]) { 

      solution[n] = true; 
      retrace(n-1,solution,target-numbers[n]); 
     } 
    } 

    else { 
     printf("\nsubset:-\n"); 
     for(int i=0;i<solution.length;i++) { 

      if(solution[i]) { 
       printf(number[i]+" "); 
      } 
     } 

    } 


} 



    Call : - retrace(numbers.length-1,new boolean[numbers.length],target); 

Answer 4

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

static void findNumbers(int[] list, int index, int current, int goal, String result) 
{ 
    if (list.length <= index || current>goal) // I've added the "=" which is missing in your code. 
      return; 
    if (current + list[index] == goal) { 
     System.out.println(result + " " + String.valueOf(list[i])); 
    } 
    else if (current + list[index] < goal) { 
     findNumbers(list, index + 1, current + list[i], goal, result + " " + String.valueOf(list[i])); 
    } 
    findNumbers(list, index + 1, current, goal, result); 
} 

В этом случае сложность будет O(2^n), который лучше для n=>5 тогда O(n!). Как было указано, сложность уменьшается, если массив сортируется. Это означает, что вы можете поместить 2-й рекурсивный вызов внутри else if, потому что вы будете уверены, что все последующие номера больше текущего list[index], что означает, что нет смысла пропускать это значение, потому что все следующие ветви этого вызова не будут генерировать никаких допустимых подмножеств.

В этом случае в худшем случае является O(2^l) где l либо индекс числа, которое больше чем ваша цель и находится в массиве, или n, если такой номер не существует.

Вызов должен быть: findNumbers(list,0,0,goal,"")