主页 / 问题 / 1094657
Accepted
Marionette
Asked:2020-03-14 23:01:45 +0000 UTC2020-03-14 23:01:45 +0000 UTC

解决“子集和问题”的时效算法

  • 772

A 是整数的集合，B 是集合 A 的子集，由恒定数量的元素组成。N 是集合 A 的元素个数，S 是子集 B 的元素之和。

也就是说，B 是集合 A 的子集，有 n 个元素，其中 n < N，其和等于 S。

N - 36, P - 编码集合 A - 7 的最大数的位数。

需要确定子集 B 的数量并找到它们。简单来说，这个任务听起来是这样的：你需要从给定的集合中找到这样的元素，使得它们的数量等于 n，并且总和严格等于 S。

你能推荐解决这个问题的最有效算法吗？

更新：这是函数现在的样子（动态编程）：

int results[A_SET_SIZE][B_SET_SUM];
for (size_t i = 0; i < A_SET_SIZE; i++) {
    results[0][B_SET_SUM - 1] = 0;
}
for (size_t i = 1; i < A_SET_SIZE; i++) {
    for (size_t j = 0; j < B_SET_SUM; j++) {
        if (j > A[i]) {
            results[i][j] = max(results[i - 1][j], results[i - 1][j - A[i]] + A[i]);
        } else {
            results[i][j] = results[i - 1][j];
        }
    }
}

使用组合公式，我们设法确定具有所需元素数量的子集的总数 - 但是如何找到正确的？或者更确切地说，如何在其中找到所有也满足总和约束的子集？

示例：该集合由 4 个元素组成（A = {1, 2, 3, 4}）。我们需要找到所有这些基数为 2 且总和为 5 的子集。事实证明，有两个子集满足这些条件：{1, 4} 和 {2, 3}。任务正是找到这样的子集。

c

3 个回答

  1. Best Answer

    演示动态规划方法：

    def findsums(l, n, summ):
    a = [[] for i in range(summ + 1)]  
    a[0].append((0,0))
    for v in l:
        for i in range(summ, v-1,-1):
            for p in a[i - v]:
                if p[1] < n:
                    a[i].append((v, p[1] + 1))
    print(a)
    return

findsums([1,2,3,4,5],2,5)

[[(0, 0)], [(1, 1)], [(2, 1)], [(2, 2), (3, 1)], [(3, 2), (4, 1)], [(3, 2), (4, 2), (5, 1)]]

    单元格a包含元组列表（您可以使用映射或数组代替元组列表），其中第一个元素是列表中最后使用的值，第二个元素是集合中的数字数量给定的总和。Sum 匹配单元格索引

    列表的最后一个单元格包含三个选项加起来最多为 5，但第三个选项来自一个术语（我在列表中添加了 5），并且不适合。选项 (3, 2) 表示和 5 由两项组成，其中最后一项是 3。要获得一组项，我们写 3，转到 5-3=2 单元格。有谎言 (2, 1)，这意味着还有一个术语是 2。类似地，我们从术语 [4,1] 中找到变体

    • 1

  2. 这个任务是在中间相遇的帮助下解决的。背包问题。适用于 2^{n/2}。

    但是，如果 S 很小，则可以使用动态规划来解决通常的背包问题。在这种情况下，运行时间将是 O(nS)

    • 0

  3. 如果我们在两种状态下进行动态处理dp[i][j]，其中i是所取元素的总和，并且我们使用索引不大于j的项目。那么答案将是dp[S][N]。我们将考虑总和等于 S 的所有集合，但如果A 的总和等于S ，那么我们将计算整个集合。在总和相等的情况下，我们只需要减去一个选项。

    dp[0][0] = 1;
for(int j = 1; j <= N; ++j) {
    for(int i = 0; i <= S; ++i){
        if(A[j] <= i){
            dp[i][j] += dp[i - A[j]][j - 1];
        }
    }
}
int ans = dp[S][N];
if(sum(A) == S) {
    ans--;
}

    注意，集合 A 中的索引从 1 开始编号

    • 0

相关问题