python - Python：在数组中查找最大元素X的子数组，其总和小于或等于给定数字

list1 = [2, 4, 6, 8, 10]

given_number = 7

问题如下：找到最大元素 X 的子数组，其总和小于或等于 Y。假设 X = 2 和 Y = 7，答案将是：[2, 4]或[6]。

现在这是一个广泛讨论的问题，我相信它被称为最大子阵列问题。然而，这个问题的非朴素解决方案只返回子数组的总和，而不提供子数组本身。这种解决方案的一个例子：

我想知道，是否有一种非天真的方式来获得这个最佳子阵列？

编辑：这个问题的一个可能答案，尽管仍然很天真（所有功劳都归我的朋友所有）：

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

标签： pythonlistsummax