0

因此，如果给我一个排序列表/数组，即 [1,6,8,15,40]，数组的大小和请求的数字..

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

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

任何帮助表示赞赏

4

2 回答 2

2

NP 完全子集和问题可以简单地简化为您的问题：给定一组整数S和一个目标值s，我们为 S 中的每个 x k 构造具有值( n + 1) x k的集合S'并设置目标等于(n+1) s。如果原始集合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 秒。

于 2012-09-26T23:06:27.130 回答
0

可能有一个更简单的解决方案，但如果您的列表足够短，您可以尝试每组值，即：

  • 1 --> 不是 23
  • 6 --> 不是 23
  • ...
  • 1 + 6 = 7 --> 不是 23
  • 1 + 8 = 9 --> 不是 23
  • ...
  • 1 + 40 = 41 --> 不是 23
  • 6 + 8 = 14 --> 不是 23
  • ...
  • 8 + 15 = 23 --> 哦，看，它是 23，我们添加了 2 个值

如果您知道您的列表已排序，则可以跳过一些测试，因为如果 6 + 20 > 23，则无需测试 6 + 40。

于 2012-09-26T23:02:05.480 回答