Как бы я отредактировал эту жадную функцию, чтобы получить сумму?

Question

Итак, я хочу создать функцию, которая принимает int s и массив 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

Функция должна возвращать список списков, потому что может быть несколько комбинаций, которые складываются в данную сумму:

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]]

Answer 2

Это был ответ раньше

Найти все комбинации списка чисел с заданной суммой

в вашем случае код:

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)