子集和的变体

Question

给定 3 个正整数 n, k, and sum，准确找到 k 个不同的元素 a_i，其中
a_i \in S, 1 <= i <= k, and a_i \neq a_j for i \neq j
并且，S 是集合
S = {1, 2, 3, ..., n}
这样
\sum_{i=1}^{k}{a_i} = sum
由于指数复杂性，我不想使用蛮力（检查所有可能的组合）来解决问题。有人可以给我一个解决这个问题的另一种方法的提示吗？此外，我们如何利用集合 S 已排序的事实？这个问题有没有可能有 O(k) 的复杂度？

Answer 1

可以修改pseudo-polynomial algorithm for subset sum。

准备一个矩阵P，维度k X sum，并将所有元素初始化为0。的含义P[p, q] == 1 是 p 个数字的子集总和为 q，并且 P[p, q] == 0表示还没有找到这样的子集

现在遍历 i = 1, ..., n。在每次迭代中：

如果i ≤ sum，设P[1, i] = 1（有一个子集尺寸 1 达到 i).
对于任何条目 P[p, q] == 1，您现在知道 P[p + 1, q + i] 现在也应该是 1。如果 (p + 1, q + i) 在矩阵的边界内，则设置 P[p + 1, q + i] = 1.

最后，检查是否 P[k, sum] == 1.

假设所有整数数学运算都是常数，复杂度是Θ(n² sum).

Answer 2

关于如何利用 1..n 设置属性的想法：

从a开始的自然行的k个连续成员之和为

sum = k*(2*a + (k-1))/2

为了获得所需 s 这样子序列的总和，我们可以求解

a >= s/k - k/2 + 1/2
or 
a <= s/k - k/2 + 1/2

比较 s 和 sum 值并进行更正。

例如，有s=173、n=40和k=5，我们可以找到

a <= 173/5 - 5/2 + 1/2 = 32.6

对于起始编号 32，我们有序列 32,33,34,35,36 和 sum = 170，对于 3 的校正，我们只需将 36 更改为 39，或将 34,35,36 更改为 35,36,37 和依此类推

似乎使用这种方法我们得到了 O(1) 复杂度（当然，可能存在一些我确实遗漏的微妙之处）

Answer 3

有一个 O(1)（可以这么说）的解决方案。接下来是@MBo 对这个想法的足够正式的（我希望）发展。

假设S是所有整数的集合并找到一个最小解就足够了。解 K 小于 K' 当且仅当 max(K) < max(K')。如果max(K) <= n，那么K也是原题的解法；否则原题无解

所以我们忽略 n 并找到 K，一个最小的解决方案。让g = max(K) = ceil(sum/k + (k - 1)/2)和s = g + (g-1) + (g-2) + ... (g-k+1)和s' = (g-1) + (g-2) + ... + (g-k)。也就是说，s' 是 s 向下移动 1。注意 s' = s - k。

显然 s >= sum 和（因为 K 最小）s' < sum.

如果 s == sum 解决方案是 K，我们就完成了。否则考虑集合 K+ = {g, g-1, ..., g-k}。我们知道 \sum(K+ \setminus {g}) < sum 和 \sum(K+ \setminus {g-k}) > sum，因此，存在 K+ 的单个元素 g_i 使得 \sum (K+ \setminus {g_i}) = sum。解决方法是K+ \setminus {\sum(K+)-sum}.

4 个整数 a, b, c, d 形式的解，其中实际集合被理解为 [a..b] \setunion [c..d] 可以在 O(1) 中计算。

Answer 4

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

unsigned long int arithmeticSum(unsigned long int a, unsigned long int k, unsigned long int n, unsigned long int *A);
void printSubset(unsigned long int k, unsigned long int *A);

int main(void)
{
    unsigned long int n, k, sum;
    // scan the respective values of sum, n, and k
    scanf("%lu %lu %lu", &sum, &n, &k);
    // find the starting element using the formula for the sum of an A.P. having 'k' terms
    // starting at 'a', common difference 'd' ( = 1 in this problem), having 'sum' = sum
    // sum = [k/2][2*a + (k-1)*d]
    unsigned long startElement = (long double)sum/k - (long double)k/2 + (long double)1/2;
    // exit if the arithmetic progression formed at the startElement is not within the required bounds
    if(startElement < 1 || startElement + k - 1 > n)
    {
        printf("-1\n");
        return 0;
    }
    // we now work on the k-element set [startElement, startElement + k - 1]
    // create an array to store the k elements
    unsigned long int *A = malloc(k * sizeof(unsigned long int));
    // calculate the sum of k elements in the arithmetic progression [a, a + 1, a + 2, ..., a + (k - 1)]
    unsigned long int currentSum = arithmeticSum(startElement, k, n, A);
    // if the currentSum is equal to the required sum, then print the array A, and we are done
    if(currentSum == sum)
    {
        printSubset(k, A);
    }
    // we enter into this block only if currentSum < sum
    // i.e. we need to add 'something' to the currentSum in order to make it equal to sum
    // i.e. we need to remove an element from the k-element set [startElement, startElement + k - 1]
    // and replace it with an element of higher magnitude
    // i.e. we need to replace an element in the set [startElement, startElement + k - 1] and replace
    // it with an element in the range [startElement + k, n]
    else
    {
        long int j;
        bool done;
        // calculate the amount which we need to add to the currentSum
        unsigned long int difference = sum - currentSum;
        // starting from A[k-1] upto A[0] do the following...
        for(j = k - 1, done = false; j >= 0; j--)
        {
            // check if adding the "difference" to A[j] results in a number in the range [startElement + k, n]
            // if it does then replace A[j] with that element, and we are done
            if(A[j] + difference <= n && A[j] + difference > A[k-1])
            {
                A[j] += difference;
                printSubset(k, A);
                done = true;
                break;
            }
        }
        // if no such A[j] is found then, exit with fail
        if(done == false)
        {
            printf("-1\n");
        }
    }
    return 0;
}

unsigned long int arithmeticSum(unsigned long int a, unsigned long int k, unsigned long int n, unsigned long int *A)
{
    unsigned long int currentSum;
    long int j;
    // calculate the sum of the arithmetic progression and store the each member in the array A
    for(j = 0, currentSum = 0; j < k; j++)
    {
        A[j] = a + j;
        currentSum +=  A[j];
    }
    return currentSum;
}

void printSubset(unsigned long int k, unsigned long int *A)
{
    long int j;
    for(j = 0; j < k; j++)
    {
        printf("%lu ", A[j]);
    }
    printf("\n");
}

子集和的变体

Variant of Subset-Sum

algorithm

set

subset-sum