algorithm - 查找列表中的最小值数以求和为值

Question

所以如果我得到一个排序列表/数组，即 [1,6,8,15,40]，数组的大小，以及请求的数字..

您如何从该列表中找到所需的最小值数以求和到所请求的数量？

例如，给定数组 [1,6,8,15,40]，我请求数字 23，它将从列表(8 和 15)中取 2 个值等于 23。然后该函数将返回 2 ( # 个值)。此外，数组中有无限数量的 1(因此您的函数将始终返回一个值)

感谢任何帮助

Answer 1

NP 完全 subset-sum problem简单地简化为您的问题:给定一个整数集 S 和一个目标值 s，我们构造具有值 ( n+1) x_k 为 S 中的每个 x_k 并将目标设置为等于(n+1) 秒。如果原始集合S的子集总和为s，那么新集合总和中最多有n的子集到 (n+1) s，这样的集合不能包含额外的 1。如果没有这样的子集，则作为答案生成的子集必须至少包含 n+1 个元素，因为它需要足够的 1 才能达到 的倍数n+1.

因此，如果不进行计算革命，该问题将不允许任何多项式时间解。排除该免责声明后，您可以考虑一些伪多项式时间解决方案，如果集合的最大尺寸较小，这些解决方案在实践中效果很好。

这里有一个 Python 算法可以做到这一点:

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 秒即可跑。