SUM 精确使用 K 元素解决方案

Question

问题：在给定的包含 N 个数字的数组中，找到大小为 M（恰好 M 个元素）等于 SUM 的子集。

我正在寻找此问题的动态规划 (DP) 解决方案。基本上是想了解矩阵填充方法。我写了下面的程序，但没有添加记忆，因为我仍然想知道该怎么做。

    #include <stdio.h>
    #define SIZE(a) sizeof(a)/sizeof(a[0])
    int binary[100];
    int a[] = {1, 2, 5, 5, 100};

    void show(int* p, int size) {
            int j;
            for (j = 0; j < size; j++)
                    if (p[j])
                            printf("%d\n", a[j]);
    }

    void subset_sum(int target, int i, int sum, int *a, int size, int K) {
            if (sum == target && !K) {
                    show(binary, size);
            } else if (sum < target && i < size) {
                    binary[i] = 1;
                    foo(target, i + 1, sum + a[i], a, size, K-1);
                    binary[i] = 0;
                    foo(target, i + 1, sum, a, size, K);
            }
    }

    int main() {
            int target = 10;
            int K = 2;
            subset_sum(target, 0, 0, a, SIZE(a), K);
    }

下面的递归解决方案是否有意义？

令 DP[SUM][j][k] 求和为从 0 到 j 个元素中恰好有 K 个元素的 SUM。

 DP[i][j][k] = DP[i][j-1][k] || DP[i-a[j]][j-1][k-1] { input array a[0....j] }

基本情况是：

DP[0][0][0] = DP[0][j][0] = DP[0][0][k] = 1
DP[i][0][0] = DP[i][j][0] = 0

这意味着我们可以考虑这个元素（DP[i-a[j]][j-1][k-1]）或者我们不考虑当前元素（DP[i][j-1] ][k]).如果我们考虑当前元素，k 减 1，这减少了需要考虑的元素，当不考虑当前元素时也是如此，即 K 不减 1。

Answer 1

我的理解，如果只是检查输入的可行性，用二维状态就可以解决问题space

bool[][] IsFeasible = new bool[n][k]

其中 IsFeasible[i][j] 是 true 当且仅当存在元素 1 到 i 的子集，其总和恰好为 j每个

1 <= i <= n
1 <= j <= k

对于这个状态space，递归关系

IsFeasible[i][j] = IsFeasible[i-1][k-a[i]] || IsFeasible[i-1][k]

可以使用

，其中 or 运算符的左侧 || 对应于选择第 i 项，右侧对应于不是选择第 i 项。项目的实际选择可以通过回溯或评估时保存的辅助信息获得。

Answer 2

我觉得你的解决方案很合适。

现在，您基本上是在回溯所有可能性并打印每个解决方案。如果您只想要一种解决方案，则可以添加一个标志，在找到一种解决方案时设置该标志，并在继续递归调用之前进行检查。

为了记忆，你应该先去掉 binary 数组，然后你可以这样做：

int memo[NUM_ELEMENTS][MAX_SUM][MAX_K]; 
bool subset_sum(int target, int i, int sum, int *a, int size, int K) {
            if (sum == target && !K) {
                    memo[i][sum][K] = true;
                    return memo[i][sum][K];
            } else if (sum < target && i < size) {
                    if (memo[i][sum][K] != -1)
                        return memo[i][sum][K];


                    memo[i][sum][K] = foo(target, i + 1, sum + a[i], a, size, K-1) || 
                                      foo(target, i + 1, sum, a, size, K);

                    return memo[i][sum][K]
            }

            return false;
    }

然后，看memo[_all indexes_][target][K]。如果这是真的，则至少存在一种解决方案。您可以存储附加信息以获得下一个解决方案，或者您可以使用从 found_index - 1 到 0 的 i 进行迭代并检查您有哪个 i memo[i][sum - a[i]][K - 1] == true.然后递归，等等。这将允许您仅使用 memo 数组重建解决方案。

SUM 精确使用 K 元素解决方案

SUM exactly using K elements solution

algorithm

recursion

recurrence

dynamic-programming