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

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

我在 Wikipedia 上找到了一个可能的起点：

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

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

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