NP完全子集和问题可以简化为您的问题:给定一组整数 S 和一个目标值 s ，我们构造具有值的集合 S' S 中每个 x _k 的(n + 1)x _k 并设置目标等于(n + 1)s .如果原始集合中有一个子集 S 总和为 s ，那么新集合中的子集大小最多为 n 到(n + 1)s ，并且这样的集合不能包含额外的1.如果没有这样的子集，那么作为答案产生的子集必须至少包含 n + 1 个元素，因为它需要足够的 1s 才能达到的倍数n + 1 .

The NP-complete subset-sum problem trivially reduces to your problem: given a set S of integers and a target value s, we construct set S' having values (n+1) x_k for each x_k in S and set the target equal to (n+1) s. If there's a subset of the original set S summing to s, then there will be a subset of size at most n in the new set summing to (n+1) s, and such a set cannot involve extra 1s. If there is no such subset, then the subset produced as an answer must contain at least n+1 elements since it needs enough 1s to get to a multiple of n+1.

因此，在不进行计算革命的情况下，该问题将不允许采用任何多项式时间解.有了这个免责声明，您可以考虑一些伪多项式时间解决方案，如果集合的最大大小很小，该方案在实践中会很好地发挥作用.

So, the problem will not admit any polynomial-time solution without a revolution in computing. With that disclaimer out of the way, you can consider some pseudopolynomial-time solutions to the problem which work well in practice if the maximum size of the set is small.

这是将执行此操作的Python算法:

Here's a Python algorithm that will do this:

import functools
S = [1, 6, 8, 15, 40] # must contain only positive integers
@functools.lru_cache(maxsize=None) # memoizing decorator
def min_subset(k, s):
    # returns the minimum size of a subset of S[:k] summing to s, including any extra 1s needed to get there
    best = s # use all ones
    for i, j in enumerate(S[:k]):
        if j <= s:
            sz = min_subset(i, s-j)+1
            if sz < best: best = sz
    return best

print min_subset(len(S), 23) # prints 2

即使对于相当大的列表(我测试了n = 50个元素的随机列表)，这也是易处理的，提供其值是有界的.使用S = [random.randint(1, 500) for _ in xrange(50)]，min_subset(len(S), 8489)的运行时间不到10秒.

This is tractable even for fairly large lists (I tested a random list of n=50 elements), provided their values are bounded. With S = [random.randint(1, 500) for _ in xrange(50)], min_subset(len(S), 8489) takes less than 10 seconds to run.