变子集琛的

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

#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"); 
} 

Answer 2

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

准备一个矩阵P与尺寸; K X总和，和所有元素初始化为0的含义P [P，Q] == 1是，有p号的一个子集总计为q和P [p，q] == 0意味着尚未找到这样的子集。

现在迭代i = 1，...，n。在每次迭代中：

1. 如果我≤总和，设置P [1，I] = 1（那里是实现我尺寸1的子集）。

2. 对于任何进入P [P，Q] == 1，现在你知道P [P + 1，Q + I]现在应该是1了。如果（p + 1，q + i）在矩阵的边界内，则设置P [p + 1，q + i] = 1。

最后，检查是否P [K，总和] == 1。

的复杂性，假定所有整数数学操作是恒定的，是Θ（N 总和）。

Answer 3

一个想法如何利用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值和make corr ections。

例如，具有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 4

有一个O（1），（这么说）解决方案。接下来的是一个正式的（我希望）由@MBo开发的想法。

假设S是一组所有整数并找到最小的解决方案就足够了。解决方案K小于K' iff 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}。

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