计算与数组重复加起来给定总和的组合的有效算法

Question

所以在个人C++项目中我遇到了一个问题。我改写如下：

给定一个包含 n 个元素的数组（例如 [1, 3, 5]，n = 3 个元素），其中 i[=第 56=] 个位置表示第 i 个索引处的数字可以取多少个可能的值（例如，这里第一个元素可以取 1 个值，即 0；第二个元素可以取 3 个值0,1,2之间；第三个元素可以取0,1,2,3,4中的5个值。

我需要列出所有可能的长度为 n 的数组，总和 小于或等于 给定数字 k。这是一个例子：

输入 1:

输入数组=[2,2]; k = 2

输出 1:

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

另外，例如：

输入 2:

输入数组=[2,2]; k = 1

输出 2:

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

问题 :

我已经编写了一个简单的递归和一个简单的迭代解决方案，它枚举了所有数组并且只保留那些总和小于k的数组。这些问题是，对于 n 很大且 k = 1 的情况，我的代码需要很长时间才能达到运行，因为它枚举了所有情况并保留了一些.

我看不到任何重叠的子问题，所以我觉得 DP 和 memoization 不适用。我怎样才能为此工作编写所需的 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; }

Answer 1

这是一个非常简单的递归任务：

#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]

Answer 2

你应该使用 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]

计算与数组重复加起来给定总和的组合的有效算法

Efficient algorithm to compute combinations with repetitions of an array adding up to given sum

c++

arrays

algorithm

counting

dynamic-programming