逻辑形式从一组数字中得到给定数字的最小UpperBound

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找到了一个线性时间算法。

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

所以，只要重复运行Pisinger的算法，增加目标和，直到得到结果？(我还没看过这篇论文，所以我不知道选择最小子集的决胜条件是否符合Pisinger算法。)