Эффективный алгоритм для вычисления комбинаций с повторениями массива с получением заданной суммы - PullRequest
Новая
       66

Эффективный алгоритм для вычисления комбинаций с повторениями массива с получением заданной суммы

0 голосов
/ 20 июня 2020

Итак, в личном C ++ проекте я столкнулся с проблемой. Я перефразирую это следующим образом:

Учитывая массив из n элементов (например, [1, 3, 5], с n = 3 элементами), где число в i -я позиция обозначает, сколько возможных значений может принимать число в i -м индексе (например, здесь первый элемент может принимать 1 значение, равное 0; второй элемент может принимать 3 значения из числа 0,1 , 2; третий элемент может принимать 5 значений из числа 0,1,2,3,4).

Мне нужно перечислить все возможные такие массивы длиной n , которые в сумме составляют меньше или равно заданному числу k . Вот пример:

Вход 1 :

input array = [2,2]; k = 2

Выход 1 :

[0,0], [0,1], [1,0], [1,1]

Также, например:

Input 2 :

input array = [2,2]; k = 1

Выход 2 :

[0,0], [0,1], [1,0]

Проблема :

Я закодировал простое рекурсивное и простое итеративное решение, которое перечисляет все массивы, а сохраняет только те, сумма которых меньше k . Проблема с ними в том, что для случая, когда n велико и k = 1 , мой код очень долго запускается, поскольку он перечисляет все случаи и сохраняет некоторые.

I не вижу перекрывающихся подзадач, поэтому я чувствую, что DP и мемоизация неприменимы. Как я могу написать требуемый код C ++ для этого, который работает?

Вот мой код для итеративной версии: 

// enumerates all arrays which sum up to k

vector<vector<int> > count_all_arrays(vector<int> input_array, int k){

    vector<vector<int> > arr;
    int n = (int)input_array.size();

    // make auxilliary array with elements

    for(int i = 0; i < n; i++){
        vector<int> temp(input_array[i]);
        std::iota(temp.begin(), temp.end(), 0);
        arr.push_back(temp);
    }

    // computes combinations

    vector<int> temp(n);
    vector<vector<int> > answers;
    vector<int> indices(n, 0);
    int next;

    while(1){ 
        temp.clear();
        for (int i = 0; i < n; i++) 
            temp.push_back(arr[i][indices[i]]);  
        long long int total = accumulate(temp.begin(), temp.end(), 0);
        if(total <= k)
            answers.push_back(temp);
        next = n - 1; 
        while (next >= 0 &&  
              (indices[next] + 1 >= (int)arr[next].size())) 
            next--; 
        if (next < 0) 
            break; 
        indices[next]++; 
        for (int i = next + 1; i < n; i++) 
            indices[i] = 0; 
    }
    return answers;
}

Ответы [ 2 ]

0 голосов
/ 20 июня 2020

Вы должны использовать dp, чтобы он работал быстро во всех случаях. Параметр dp [i] [j] означает, сколько способов вы используете первый элемент j для создания суммы, которая меньше или равна i. 

dp[i][j] = dp[

for (int l = 0; l <= i; l++) 
    dp[i][j] += dp[l][j] + min(i-l+1, input[j])

Результат: dp [k, n]

0 голосов
/ 20 июня 2020

Это довольно простая рекурсивная задача: 

#include <bits/stdc++.h>    
using namespace std;

int arr[] = {2, 2};
int n = 2;
int k = 2;

void gen(int pos, int sum, string s){
    if(pos == n){
        cout<<"["<<s<<" ]"<<endl;
        return;
    }
    for(int i = 0; i < arr[pos]; i++){
        if(sum + i > k) return;
        gen(pos + 1, sum + i, s + " " + to_string(i));
    }
}

int main(){
    gen(0, 0, "");
    return 0;
}

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

Когда n большой и k = 1, естественно, что он принимает O (n), так как у вас будет: 

[0, 0, 0, ..., 0, 0, 1]
[0, 0, 0, ..., 0, 1, 0]
[0, 0, 0, ..., 1, 0, 0]
          ...
[0, 0, 1, ..., 0, 0, 0]
[0, 1, 0, ..., 0, 0, 0]
[1, 0, 0, ..., 0, 0, 0]
...