在列表中查找要求和的最小数量的值 [英] Finding the minimum number of values in a list to sum to value

问题描述

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

So if I was given a sorted list/array i.e. [1,6,8,15,40], the size of the array, and the requested number..

您将如何从该列表中找到所需的最小数目的值，以求和成请求的数目?

How would you find the minimum number of values required from that list to sum to the requested number?

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

For example given the array [1,6,8,15,40], I requested the number 23, it would take 2 values from the list (8 and 15) to equal 23. The function would then return 2 (# of values). Furthermore, there are an unlimited number of 1s in the array (so you the function will always return a value)

感谢您的帮助

推荐答案

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.

这篇关于在列表中查找要求和的最小数量的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！