рекурсивная функция для задачи разбиения

Question

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

Например, существует два способа разбить набор {1, 3, 4, 5} так, чтобы оставшиеся элементы складывались в 5:

• Выберите 1 и 4
• Выберите только 5

В отличие от этого, нет способа разбить набор {1, 3, 4, 5}, чтобы получить 11.

#include "genlib.h"
#include <iostream>

void RecursePart(int[], int, int, int&);
int Wrapper(int[], int, int);


int main() {
    int arr[8] = {1,2,3,4,5,6,7,8};
    cout << Wrapper(arr, 8, 11);
}


void RecursePart(int arr[], int len, int target, int& ctr) {
    if (len == 1) {
        if (arr[0] == target) {
            ctr++;
        }
        return; 
    }

    int sum, temp;
    sum = temp = arr[0];

    for (int j = 1; j < len; j++) {
        if (sum == target) {
            ctr++;
            break;
        }

        sum = sum + arr[j];

        if (sum == target) {
            ctr++;
            sum = temp;
            continue;           
        }

        if (sum > target) {
            sum = temp;
            continue;
        }

        if (sum < target) {
            temp = sum;
            continue;
        }    
    }

    RecursePart(arr + 1, len - 1, target, ctr);
}

int Wrapper(int arr[], int len, int target) {
    int n = 0;
    RecursePart(arr, len, target, n);
    return n;
}

Проблема заключается вчто вывод, который я получаю, равен 1, но количество раз, когда подмножество чисел в массиве, которое составляет до 11, больше, чем просто 1. Я попытался отследить алгоритм, и я знаю, что проблема должна быть в цикле for,Там алгоритм пропускает некоторые суммы.Как я мог преодолеть эту проблему?

Answer 1

Как и другие заявленные, это проблема суммы подмножеств (которая является NP-полной), то есть вам нужен экспоненциальный алгоритм времени для ее решения.
Просто взглянув на свою функцию, вы вызываете RecursePart один раз, каждый раз с len-1, а затем получаете for-loop длины n, что означает, что ваши вычисления равны O(n^2). Это, очевидно, не решит проблему O(2^n).

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

int RecursePart(int arr[], int len, int idx, int curr_sum, int target)     
{        
    int count = 0;

    // this subset is good
    if (curr_sum == target)
       return 1;

    // the sum of the current subset exceeds target, no point in continuing
    if (curr_sum > target || idx == len)
       return 0;

    count += RecursePart(arr, len, idx+1, curr_sum + arr[idx], target);
    count += RecursePart(arr, len, idx+1, curr_sum, target);

    return count;
}

Это мое предыдущее решение, которое создает все возможные подмножества, и подсчитываются те, которые соответствуют цели.

#include <iostream>

int Wrapper(int[], int, int);

int main() {
    int arr[8] = {1,2,3,4,5,6,7,8};
    std::cout << Wrapper(arr, 8, 11);
}

// counts the sum of a subset
int CountSet(int* arr, int* mask, int len)
{
    int sum = 0;

    for (int i=0; i < len; ++i)
    {
        if (mask[i])
        {
            sum += arr[i];
        }
    }
    return sum;
}


int RecursePart(int arr[], int idx, int len, int* subset_mask, int target) 
{
    int count = 0;

    if (idx == len)
    {
        if (CountSet(arr, subset_mask, len) == target)
            return 1;
        else
            return 0;
    }

    // create the subset "without" me
    subset_mask[idx] = 0;
    count += RecursePart(arr, idx+1, len, subset_mask, target);

    // now create the subset "with" me
    subset_mask[idx] = 1;
    count += RecursePart(arr, idx+1, len, subset_mask, target);

    return count;
}

int Wrapper(int arr[], int len, int target) {

    int* subset_mask = (int*)malloc(len*sizeof(int));
    int res = RecursePart(arr, 0, len, subset_mask, target);
    free(subset_mask);
    return res;
}

Answer 2

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

Answer 3

Поскольку вы используете C ++, вы также можете использовать vector<int> для хранения следующих промежуточных решений:

#include <iostream>
#include <vector>

using namespace std;

vector<int> RecursePart(int[], int, int, int&);
int Wrapper(int[], int, int);


int main() {
    int arr[8] = {8,2,3,4,5,6,7,1};
    cout << Wrapper(arr, 8, 11);
}


vector<int> RecursePart(int arr[], int len, int target, int& ctr) 
{
    vector<int> return_vec;

    if (len == 1)
    {
        if (arr[0] == target)
        {
            ctr++;
            return return_vec;
        }

        return_vec.push_back(arr[0]);
        return return_vec;
    }

    int current = arr[0];

    if (current == target)
        ctr++;

    if (current < target)
        return_vec.push_back(current);

    vector<int> temp;

    temp = RecursePart(arr + 1, len - 1, target, ctr);

    for (int i = 0; i < temp.size(); i ++)
    {
        if (temp[i] + current == target)
        {
            ctr++;
        }

        if (temp[i] + current < target)
            return_vec.push_back(temp[i] + current);

        if (temp[i] < target)
            return_vec.push_back(temp[i]);
    }

    /*Debug Print
    cout << "Current: " << current << endl;
    for (int i = 0 ; i < return_vec.size(); i++)
    {
        cout << return_vec[i] << ", ";
    }
    cout << endl;
    */

    return return_vec;
}

int Wrapper(int arr[], int len, int target) {
    int n = 0;
    RecursePart(arr, len, target, n);
    return n;
}

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

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