寻求从列表中筛选满足总和<90且移除元素最少的最优组合方案

你的问题本质是最大化保留元素数量，同时满足保留元素的总和小于90——这和“移除元素数量最少”是等价的。下面针对你的案例给出两种可行方案：

一、暴力枚举法（适合小列表） #

因为你的列表只有9个元素，组合数可控，用itertools.combinations直接枚举是最快的实现方式。

核心思路 #

1. 先计算原列表总和：[3,2,5,8,9,11,45,12,44]的总和是139，远大于90，所以不可能保留全部元素。
2. 从“保留最多元素”的情况往下遍历：先检查保留8个元素的组合（移除1个），再检查保留7个（移除2个），直到找到总和<90的组合——第一个找到的就是最优解（因为保留元素最多）。

代码示例 #

import itertools

lst = [3,2,5,8,9,11,45,12,44]
target_max = 90

# 从最多保留元素开始遍历
for keep_count in range(len(lst), 0, -1):
    # 生成所有保留keep_count个元素的组合
    for combo in itertools.combinations(lst, keep_count):
        if sum(combo) < target_max:
            print(f"最优组合（保留{keep_count}个元素）：{combo}")
            print(f"组合总和：{sum(combo)}")
            exit()  # 找到第一个最优解就退出
print("无符合条件的组合")

优化技巧 #

可以先计算需要移除的最小元素和：需要移除的和 ≥ 原总和 - (target_max - 1)，即139-89=50。因为单个元素最大是45<50，所以移除1个元素不可能满足，直接从保留7个元素（移除2个）开始枚举，减少不必要的计算。

二、整数规划法（适合大列表） #

如果列表元素数量较多（比如20个以上），暴力枚举会因为组合数爆炸变得低效，这时用Google OR-Tools的整数规划求解器更合适。

核心思路 #

把问题建模为整数规划问题：

• 给每个元素定义一个0-1变量：x_i=1表示保留该元素，x_i=0表示移除。
• 目标函数：最大化sum(x_i)（即保留最多元素）。
• 约束条件：sum(x_i * 元素值) < 90。

代码示例 #

from ortools.linear_solver import pywraplp

lst = [3,2,5,8,9,11,45,12,44]
target_max = 90

# 创建SCIP求解器（OR-Tools支持多种求解器）
solver = pywraplp.Solver.CreateSolver('SCIP')
if not solver:
    print("无法创建求解器")
    exit()

# 定义0-1变量：每个元素对应一个变量
x = [solver.IntVar(0, 1, f'x_{i}') for i in range(len(lst))]

# 设置目标：最大化保留的元素数量
solver.Maximize(solver.Sum(x))

# 添加约束：保留元素的总和必须小于90
solver.Add(solver.Sum([x[i] * lst[i] for i in range(len(lst))]) < target_max)

# 求解
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print(f"最多可保留{int(solver.Objective().Value())}个元素")
    retained_elements = [lst[i] for i in range(len(lst)) if x[i].solution_value() == 1]
    print(f"保留的元素：{retained_elements}")
    print(f"组合总和：{sum(retained_elements)}")
else:
    print("无符合条件的组合")

优势 #

求解器会用优化算法（如分支定界）快速找到最优解，不需要遍历所有可能的组合，效率远高于暴力法。

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