从数字集合中得到给定数字的最小上界的逻辑形式

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，等等。

所以只要反复运行Pisinger算法，不断增加目标和，直到你得到结果?(我没有看过论文，所以不知道Pisinger算法是否满足选择最小子集的破局条件)