алгоритма, чтобы получить подмножество массива с целевой суммой не дает работать

Question

задачи дается несортированный массив, дать подмножество массива, которые могут производить целевую сумму:

Для например:

target = 15 
data = {3,4,5,7,1,2,9}; 

Ожидаемого результатам (обратите внимание на результаты сортируются для простоты не является обязательным требованием.):

[1, 2, 3, 4, 5] 
[1, 2, 3, 9] 
[1, 2, 5, 7] 
[1, 3, 4, 7] 
[1, 5, 9] 
[2, 4, 9] 
[3, 5, 7] 

Вот мой наивный подход к этой проблеме - простой и грубая сила.

public static void naiveSubset(int[] arr, int target){ 
     int sum=0; 
     List<Integer> result = new ArrayList<>(); 
     for (int i=0; i< arr.length;i++){ 
       sum =arr[i]; 
       result.add(arr[i]); 
     for (int j=0;j<arr.length;i++){ 
      if (sum==target){ 
       System.out.println(result); 
       result.clear(); 
       break; 
      } 
      else if (i!=j && sum+arr[j] <= target){ 
       sum+=arr[j]; 
       result.add(arr[j]); 
       } 
      } 
     } 
     } 

По некоторым причинам я не ожидаю результатов. Я пробовал просматривать код, чтобы выкапывать любые проблемы. Но я не мог найти. пожалуйста, эксперты-эксперты, укажите меня в правильном направлении!

Результаты я получаю (на тот же вход, как описано выше)

[3, 3, 3, 3, 3] 
[9, 3, 3] 

Answer 1

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

Однако этот жадный подход не работает, с простым примером следующего массива: [1,9,6,5] и с sum=11.

Обратите внимание, что для любого элемента, который вы выбираете во внешнем цикле, затем вы добавите 1 к текущему набору. Но это лишит вас возможности получить сумму 5+6.
Как только вы выберете 5, вы начнете добавлять число, начиная с '1', и добавив его. Как только он будет добавлен, вы никогда не получите правильное решение.

Также обратите внимание: Вашего подход двойного цикла может генерировать максимум O(n^2) различных подмножеств, но может быть экспоненциальным числом подмножеств - так что-то должно быть неправильным.

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

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

Вот простой Java код, который делает это:

public static void getAllSubsets(int[] elements, int sum) { 
    getAllSubsets(elements, 0, sum, new Stack<Integer>()); 
} 
private static void getAllSubsets(int[] elements, int i, int sum, Stack<Integer> currentSol) { 
    //stop clauses: 
    if (sum == 0 && i == elements.length) System.out.println(currentSol); 
    //if elements must be positive, you can trim search here if sum became negative 
    if (i == elements.length) return; 
    //"guess" the current element in the list: 
    currentSol.add(elements[i]); 
    getAllSubsets(elements, i+1, sum-elements[i], currentSol); 
    //"guess" the current element is not in the list: 
    currentSol.pop(); 
    getAllSubsets(elements, i+1, sum, currentSol); 
} 

Обратите внимание, что если вы ищете для всех подмножеств, не может быть экспоненциальным число тех, кто - так неэффективное и экспоненциальное решение времени, как ожидается.

---

Если вы ищете для поиска, если такой набор существует, или найти только один такой набор, это можно сделать гораздо более эффективно с помощью динамического программирования. This thread объясняет логику того, как это можно сделать.
Обратите внимание, что проблема по-прежнему NP-Hard, и «эффективное» решение на самом деле является только псевдополиномиальным.

Answer 2

Я думаю, что основная проблема в вашем предыдущем подходе состоит в том, что простое выполнение циклов на основе входного массива не будет охватывать все комбинации чисел, соответствующих целевому значению. Например, если ваш основной цикл находится в ith, и после того, как вы перейдете через элемент jth во вторичный цикл, ваша будущая комбинация, основанная на том, что вы собрали через i-й элемент, больше не будет включать jth. Интуитивно говоря, этот алгоритм будет собирать все видимые комбинации через числа рядом друг с другом, но не далеко друг от друга.

Я написал итеративный подход, чтобы справиться с этой проблемой суммы подмножества через C++ (извините, у меня нет среды java: P), идея в основном такая же, как и рекурсивный подход, что означает, что вы записываете все существующие комбинации чисел во время каждой итерации в вашем цикле. У меня есть один vector<vector> intermediate, используемый для записи всей встреченной комбинации, значение которой меньше цели, а vector<vector> final используется для записи всех комбинаций, сумма которых равна цели.

Подробное объяснение записывается рядный:

/* sum the vector elements */ 
int sum_vec(vector<int> tmp){ 
    int sum = 0; 
    for(int i = 0; i < tmp.size(); i++) 
     sum += tmp[i]; 
    return sum; 
} 

static void naiveSubset(vector<int> arr, int target){ 
    /* sort the array from big to small, easier for us to 
    * discard combinations bigger than target */ 
    sort(arr.begin(), arr.end(), greater<int>()); 

    int sum=0; 
    vector<vector<int> > intermediate; 
    vector<vector<int> > final; 
    for (int i=0; i< arr.size();i++){ 
     int curr_intermediate_size = intermediate.size(); 
     for(int j = 0; j < curr_intermediate_size; j++){ 
      int tmpsum = sum_vec(intermediate[j]); 
      /* For each selected array element, loop through all 
      * the combinations at hand which are smaller than target, 
      * dup the combination, put it into either intermediate or 
      * final based on the sum */ 
      vector<int> new_comb(intermediate[j]); 
      if(tmpsum + arr[i] <= target){ 
       new_comb.push_back(arr[i]); 
       if(tmpsum + arr[i] == target) 
        final.push_back(new_comb); 
       else 
        intermediate.push_back(new_comb); 
      } 
     } 
     /* finally make the new selected element a separate entry 
     * and based on its value, to insert it into either intermediate 
     * or final */ 
     if(arr[i] <= target){ 
      vector<int> tmp; 
      tmp.push_back(arr[i]); 
      if(arr[i] == target) 
       final.push_back(tmp); 
      else 
       intermediate.push_back(tmp); 
     } 
    } 
    /* we could print the final here */ 
} 

Просто написал так, пожалуйста, медведь со мной, если есть угол так, что я не считал хорошо. Надеюсь, это поможет :)