Подмножество Сумма плавает Elimations

Это возможное решение, но это не красиво:

import itertools
import operator
from functools import reduce

def subset_num(array, num):
subsets = reduce(operator.add, [list(itertools.combinations(array, r)) for r in range(1, 1 + len(array))])
return [subset for subset in subsets if sum(subset) == num]print(subset_num([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20))

Выход:

[(20,), (11.96, 8.04), (9, 11), (11, 9), (1, 10, 9), (1, 10, 9), (7.8, 11.13, 1.07)]

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: это не полное решение, это способ просто помочь вам создать возможные подмножества. Это не поможет вам выбрать, какие из них идут вместе (без использования одного и того же предмета более одного раза и получения наименьшего остатка).

Используя динамическое программирование, вы можете построить все подмножества, которые складываются в заданную сумму, тогда вам нужно будет просмотреть их и найти, какая комбинация подмножеств лучше всего подходит для вас.

Чтобы построить этот архив, вы можете (я предполагаю, что мы имеем дело только с неотрицательными числами) поместить элементы в столбец, перейти сверху вниз и для каждого элемента вычислить все подмножества, которые складываются в сумму или меньшее число, чем оно, и включает только элементы из столбца, которые находятся в том месте, на которое вы смотрите, или выше. Когда вы строите подмножество, вы помещаете в его узел как сумму подмножества (которая может быть заданной суммой или меньше), так и элементы, включенные в подмножество. Таким образом, чтобы вычислить подмножества для элемента [i], вам нужно только взглянуть на подмножества, которые вы создали для элемента [i-1]. Для каждого из них есть 3 варианта:

1) сумма подмножества является заданной суммой —> Сохраните подмножество как есть и перейдите к следующему.

2) сумма подмножества меньше заданной суммы, но больше ее, если к ней добавлен элемент [i] —> сохранить подмножество таким, как оно есть, и перейти к следующему.

3) сумма подмножества меньше заданной суммы, и она все равно будет меньше или равна ей, если к ней будет добавлен элемент [i] —> Сохраните одну копию подмножества такой, какая она есть, и создайте еще одну с элементом [ я] добавил к нему (как в качестве члена и добавлен к сумме подмножества).

Когда вы закончите с последним элементом (item [n]), посмотрите на подмножества, которые вы создали — каждый из них имеет свою сумму в своем узле, и вы можете увидеть, какие из них равны данной сумме (а какие меньше — они вам больше не нужны).

Как я писал в начале — теперь вам нужно выяснить, как выбрать лучшую комбинацию подмножеств, которые не имеют общего члена между ними.
По сути, у вас осталась проблема, похожая на классическую проблему ранца, но с другим ограничением (не каждый камень можно взять с любым другим камнем). Может быть, ограничение действительно помогает, я не уверен.

Еще немного о преимуществах динамического программирования в этом случае

Основная идея динамического программирования вместо рекурсии заключается в обмене избыточностью операций с использованием пространства памяти. Под этим я подразумеваю, что рекурсия со сложной проблемой (как правило, с проблемой рюкзака, как у нас здесь) обычно заканчивает тем, что вычисляет одну и ту же вещь довольно много раз, потому что разные ветви вычисления не имеют понятия друг о друге. операции и результаты. Динамическое программирование сохраняет результаты и использует их в процессе создания «больших» результатов, опираясь на предыдущие / «меньшие» результаты. Поскольку использование стека намного проще, чем при рекурсии, у вас не возникает проблем с памятью, которые вы получаете с рекурсией относительно поддержания состояния функции, но вам нужно обрабатывать большое количество памяти, которую вы храните (иногда Вы можете оптимизировать это).

Так, например, в нашей задаче, пытаясь объединить подмножество, которое бы суммировалось до требуемой суммы, ветвь, которая начинается с элемента A, и ветвь, которая начинается с элемента B, не знают операций друг друга. давайте предположим, что элемент C и элемент D вместе складываются в сумму, но любой из них, добавленный в одиночку к A или B, не превысит сумму, и что A не идет с B в решении (у нас может быть sum = 10, A = B = 4, C = D = 5, и нет подмножества, которое суммирует до 2 (поэтому A и B не могут быть в одной группе)). Ветвь, пытающаяся выяснить группу A, (после попытки и отказа от наличия B в своей группе) добавит C (A + C = 9), а затем добавит D, после чего точка отклонит эту группу и trackback (A + C + D = 14> сумма = 10). Конечно, то же самое произошло бы с B (A = B), потому что ветвь, определяющая группу B, не имеет информации относительно того, что только что произошло с веткой, имеющей дело с A. Так что на самом деле мы вычислили C + D дважды, и не даже использовал его еще (и мы собираемся вычислить это в третий раз, чтобы понять, что они принадлежат к своей группе).

НОТА:
Оглядываясь при написании этого ответа, я наткнулся на технику, с которой я не был знаком и мог бы стать для вас лучшим решением: запоминание. Взято из википедия:

Запоминание — это метод оптимизации, который используется главным образом для ускорения работы компьютерных программ за счет сохранения результатов дорогостоящих вызовов функций и возврата кэшированных результатов при повторных вводах.

Итак, у меня есть возможное решение:

    #compute difference between 2 list but keep duplicates
def list_difference(a, b):
count = Counter(a) # count items in a
count.subtract(b)  # subtract items that are in b
diff = []
for x in a:
if count[x] > 0:
count[x] -= 1
diff.append(x)
return diff#return combination of numbers that match target
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print "--------------------------------------------sum_is(%s)=%s" % (partial, target)
return partial
else:
if s >= target:
return  # if we reach the number why bother to continue

for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
rest = subset_sum(remaining, target, partial + [n])
if type(rest) is list:
#repeat until rest is > target and rest is not the same as previous
def repeatUntil(subset, target):
currSubset = []
while sum(subset) > target and currSubset != subset:
diff = subset_sum(subset, target)
currSubset = subset
subset = list_difference(subset, diff)
return subset

Выход:

--------------------------------------------sum_is([11.96, 8.04])=20
--------------------------------------------sum_is([1, 10, 9])=20
--------------------------------------------sum_is([7.8, 11.13, 1.07])=20
--------------------------------------------sum_is([20])=20
--------------------------------------------sum_is([9, 11])=20
[15.04]

К сожалению, это решение работает для небольшого списка. Для большого списка все еще пытаются разбить список на маленькие куски и подсчитать, но ответ не совсем верен. Вы можете увидеть это в новой теме здесь:
Поиск уникальных комбинаций чисел для достижения заданной суммы