Python求解从列表选两个不交子集和分别≤X、Y的最大元素总数问题

要最大化选中元素的数量，核心原则是优先选择数值最小的元素：相同数量下，数值越小总和越低，越容易满足两个子集的和限制。
步骤如下：

1. 将输入数组按升序排序
2. 从最大可能的选中数量（即数组总长度）开始向下遍历，逐个判断当前数量k是否可行：
   • 取排序后的前k个最小元素，计算它们的总和sum_k
   • 如果sum_k > X + Y：直接跳过，两个子集加起来最多只能装X+Y，总和超了肯定无法满足
   • 否则只需判断：是否能从前k个元素中选出一个子集，满足sum(子集) ≤ X 且 sum_k - sum(子集) ≤ Y，等价于子集和落在区间[sum_k - Y, X]内
   • 如果存在这样的子集，说明k是可行的，直接返回k即可

def max_selected_elements(n, X, Y):
    n_sorted = sorted(n)
    max_possible = len(n_sorted)
    # 从最大可能的数量往下遍历，找到第一个可行值就是最优解
    for k in range(max_possible, -1, -1):
        if k == 0:
            return 0
        arr = n_sorted[:k]
        sum_k = sum(arr)
        # 总和超过两个阈值之和直接不可能
        if sum_k > X + Y:
            continue
        # 子集和需要满足的区间范围
        low = sum_k - Y
        high = X
        if low > high:
            continue
        # 01背包计算所有不超过high的子集和
        dp = [False] * (high + 1)
        dp[0] = True
        for num in arr:
            for s in range(high, num - 1, -1):
                if dp[s - num]:
                    dp[s] = True
        # 检查是否有子集和落在目标区间
        for s in range(low, high + 1):
            if dp[s]:
                return k
    return 0

# 测试样例
if __name__ == "__main__":
    # 示例1
    print(max_selected_elements([5, 5, 4, 6], 8, 8))  # 输出2
    # 示例2
    print(max_selected_elements([6,5,2,1,8], 17, 5))  # 输出5
    # 示例3
    print(max_selected_elements([6,5,5,4,3], 8, 9))  # 输出4

• 排序后从最大可选数向下遍历，第一个满足条件的k就是最大值，不需要再校验更小的k
• 提前过滤sum_k > X+Y的无效场景，大幅减少不必要的背包计算
• 背包仅计算到上限X即可，空间复杂度和时间复杂度都控制在合理范围

内容的提问来源于stack exchange，提问作者akshay