在列表中查找总和等于给定值的数值

Question

我正在尝试编写一个简单且符合Python规范的代码，用于识别列表中值的组合，这些值的总和在一定公差内等于给定的值。

例如： 如果A=[0.4,2,3,1.4,2.6,6.3]，目标值为5 +/- 0.5，则我想要的输出结果是(2,3), (1.4,2.6), (2,2.6), (0.4,2,3), (0.4,3,1.4)等。如果找不到任何组合，则函数应该返回0或none或类似的结果。

非常感谢您的帮助。

- Mark

---

这是一个NP完全问题：http://en.wikipedia.org/wiki/Subset_sum_problem - Tuan Anh Hoang-Vu

如果你能在多项式时间内以100%的正确率解决这个问题，告诉我吧 ;) 我们可以成为好基友 :D - Yeo

让我们来看看，这是近似算法。 - Yeo

我在面试中被问到了几乎相同的问题，但我不知道答案 :( - hyades

@hyades 哎呀！那是一个非常困难的面试问题！！ - Mark

Answer 1

请查看 itertools.combinations。

def first_attempt(A=A):
        for i in xrange(1,len(A)+1):
                print [comb 
                                for comb in list(itertools.combinations(A,i)) 
                                if 4.5 < sum(map(float, comb)) < 5.5
                                ]
## -- End pasted text --

In [1861]: %timeit first_attempt
10000000 loops, best of 3: 29.4 ns per loop

输出 -

In [1890]: first_attempt(A=A)
[]
[(2, 3), (2, 2.6)]
[(0.4, 2, 3), (0.4, 2, 2.6), (0.4, 3, 1.4)]
[]
[]
[]

- fixxxer

---

你可以通过以下代码将列表中大于4.5的值过滤掉：A = filter(lambda x: x < 4.5, A)。 - Tiger-222

@Mark 2^n算法。所以不会很好地扩展。 - hyades

@Tiger-222 这将会移除这些元素 - (0.4,2,3)。不是吗？ - fixxxer

@fixxxer 不是的，我犯了一个错误，它是5.5而不是4.5。它将返回 [0.4, 2, 3, 1.4, 2.6]。 - Tiger-222

谢谢你的解释。我一定会尝试使用递归算法。 - Mark

Answer 2

这里是一种递归的方法:

以下是需要翻译的内容：

# V is the target value, t is the tolerance
# A is the list of values
# B is the subset of A that is still below V-t
def combination_in_range(V, t, A, B=[]):
    for i,a in enumerate(A):
        if a > V+t:    # B+[a] is too large
            continue

        # B+[a] can still be a possible list
        B.append(a)

        if a >= V-t:   # Found a set that works
            print B

        # recursively try with a reduced V
        # and a shortened list A
        combination_in_range(V-a, t, A[i+1:], B)

        B.pop()        # drop [a] from possible list

A=[0.4, 2, 3, 1.4, 2.6, 6.3]
combination_in_range(5, 0.5, A)

- Brent Washburne

---

很好的回答。最后一行有一个小错别字，应该调用combination_in_range而不是re。 - Tiger-222

谢谢你发现了这个问题。我已更新代码，使用更好的名称和注释，并遗漏了最后一行。现在已修复。 - Brent Washburne

我如何使用这个来返回所有的值？ - aldoblack