从数字集中获取给定数字的最小上界的逻辑形式

Question

我的问题如下-

我有一些数字，如下所示-

  2
  2
  2
  2
  3
  3
 17
 17
 17
 17
 17
 17
 17
 17
 17
 34
 34
 34
 34
 34
 68
 68
 68
136

所以如果我给出以下数字作为输入，输出应如下-

[输出是给定数字的总和， 刚刚大于输入]

 Input  Output
     3      2,2
     4      2,2
     254    17,34,68,136
     7      2,3,3 [or also with 2,2,2,2 but if return same sum,
                   then number count should min]
     205    2,68,136
     10     2,2,3,3

我不想尝试每一个组合（即暴力）来获得结果。所以想问一下有没有什么有效的算法可以解决上述情况。

谢谢。

Answer 1

我在维基百科上找到了一个可能的起点：

一个更普遍的问题要求子集求和为指定值（不一定为 0）。通过对上述算法进行简单修改即可解决。对于每个 xi 为正且受同一常数限制的情况，Pisinger 找到了线性时间算法。[3]

您的基本问题看起来像是该问题的扩展版本。您需要找到集合的一个子集，求和为 input - 或者失败，求和为 input+1，或者失败，求和为 input+2< /code> 等。

所以只要重复运行 Pisinger 算法，增加目标总和，直到得到结果？ （我没有读过论文，所以不知道Pisinger算法是否满足选择最小子集的决胜条件。）