将一个数表示为数组的子集的和

Question

给定一个自然数S>10，我想生成一个由N个自然数A= (a1，a2，…)组成的数组，aK，…，aN)使得S是M的和。

约束1：

ai < S/2

约束2：

M >= K

约束3(可选)：ai != aj

对不起，我不确定如何使用适当的数学符号来描述这个问题，但是想法很简单:生成一些值，这些值加起来就是一个预定义的总数。然后添加一些更多的值(所谓的“诱饵”)，使选择要使用的正确值的任务变得更加困难。

假设S=18和我希望它表示为至少3个值的总和。因此，“获胜”数组应该是A=(7,8,3,4,5)，因为7+8+3=18和没有办法使用少于3的值来获得18。

我已经有了一个简单的算法，有点效果：

Input: 
S - the sum
K - the number of values required to add up to S
N - the total number of values (includes the decoys)

Output: 
A - the array of values ai

1) Generate K values by dividing S by K and then adding and subtracting some random numbers. This ensures that ai will be more or less random while still adding up to S.

2) Generate (N-K) random values less than S/2 each.

3) Combine all the generated values into one array A.

4) Test that S can be represented as a sum of no less than K values from the array A. If not, discard A and return to 1)

Example:
S = 20
K = 3
N = 5
ai values generated: 7, 1, 12, 4, 8,
7+1+12=20 – This is what we need (3 values add up to 20)

But we also can get 20 with only 2 values and this violates Constraint 2:
12+8 = 20

当然，这是一种蛮力方法，我检查了太多的迭代，但这显然不是正确的方法。

我的问题是:是否有可能生成数组A，使其自动满足约束1,2,3或至少满足约束1,2？

Answer 1

对于正整数，简短的答案是否定的:反例S=1 K=2。

createLongList(S,K)
{
  list= {};
  for(i=1 to s/2)
    if(canAdd(list,S,K,i))
      list.add(i);
    else break;
}

这会创建一个最大尺寸列表吗？也许不是，但它会做得很好。没有进入数学，递归搜索将给出一个保证最好的结果。

#list=={} the first time, istart=S/2
createLongList(S,list,K,istart)
{
  bestList=list;
  for(i=istart to 1)
     if(canAdd(list,S,K,i))
       newList=createLongList(S,list++i,K,i-1);
       if(newList.isLongerThan(bestList))
         bestList=newList;
  return bestList;
}