我将如何编辑这个贪婪的函数来给我一个总和？

Question

所以，我想创建一个函数，它接受 int s 和数组 A，然后返回加起来为 s 的元素数组 A。如果没有子集，则应返回最接近 s 的值。例如：A = [12, 79, 99, 91, 81, 47]s = 150将返回：[12, 91, 47]为12 + 91 + 47是150。以下是我到目前为止所拥有的。我究竟做错了什么？def closest(s, A):    if s == 0:        return 0    for i in range(len(A)):        if A[i] <= s:            return 1 + closest(s - A[i], A)

Answer 1

在您的情况下，代码是：

import itertools

def itersum(nums, target):

    result = [seq for i in range(len(nums),0,-1) for seq in itertools.combinations(nums,i) if sum(seq) == target]

    if result != target:

       for j in range(target):

           result1 = [seq for i in range(len(nums),0,-1) for seq in itertools.combinations(nums,i) if sum(seq) == target + j]

           result2 = [seq for i in range(len(nums),0,-1) for seq in itertools.combinations(nums,i) if sum(seq) == target - j]

           if (len(result1) + len(result2)) > 0:

               result = result1 if result1 > result2 else result2

               break            

    return result

A = [12, 79, 99, 91, 81, 44]

s = 150

itersum(A, s)

Answer 2

该函数应该返回一个列表列表，因为可能有多个组合加起来为给定的总和：

def closest(s, A):

    if s == 0:

        return [[]]

    o = []

    for i, n in enumerate(A):

        if n <= s:

            for c in closest(s - n, A[i + 1:]):

                o.append([n] + c)

    return o

以便：

closest(150, [12, 79, 99, 91, 81, 47])

返回：

[[12, 91, 47]]

然后：

closest(10, [4, 5, 6, 2, 1, 3])

返回：

[[4, 5, 1], [4, 6], [4, 2, 1, 3], [5, 2, 3], [6, 1, 3]]