list1 = [2, 4, 6, 8, 10]
given_number = 7
Проблема заключается в следующем: Найти подмассив с максимальными элементами X, сумма которых меньше или равна Y. Допустим, X = 2 и Y = 7, ответ будет: [2, 4] или [6].
Теперь это широко обсуждаемая проблема, я думаю, что она называется проблемой максимального подмассива. Однако не наивное решение этой проблемы возвращает только сумму подмассива и не предоставляет сам подмассив. Пример такого решения:
https://www.geeksforgeeks.org/maximum-sum-subarray-sum-less-equal-given-sum/?ref=lbp
Мне интересно, есть ли не наивный способ получения этого оптимального подмассива?
РЕДАКТИРОВАТЬ: Возможный ответ на эту проблему, хотя все еще наивный (все кредиты для этого идет к моему другу):
1) Создайте все комбинации подмножеств с помощью itertools:
combs = [list(x) for x in itertools.combinations(list1, number_of_elements)]
2) Сортировка по размеру суммы:
sorted_combs = sorted(combs, key=lambda x: sum(x), reverse=True)
3) Возьмите первую сумму, меньшую или равную данной сумме:
given_sum = 7
optimal_subset = None
for sc in sorted_combs:
if sum(sc) <= given_sum:
optimal_subset = sc
break