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

Question

所以，我想创建一个函数，它接受 int s 和数组 A，然后返回元素 A 组成的数组，其中元素 A 的总和为 s。如果没有子集，应返回最接近 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

这个问题之前已经回答过

Find all combinations of a list of numbers with a given sum

在您的情况下，代码是:

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)