本文介绍一种基于 itertools.combinations 的精确求解方法，用于在满足两个兼容性列表中各自至少选中指定数量元素的前提下，找出总成本最小的索引子集。适用于小规模实例（n ≤ 20），逻辑清晰、实现简洁、结果可靠。
本文介绍一种基于 itertools.combinations 的精确求解方法，用于在满足两个兼容性列表中各自至少选中指定数量元素的前提下，找出总成本最小的索引子集。适用于小规模实例（n ≤ 20），逻辑清晰、实现简洁、结果可靠。
在实际优化场景中，我们常遇到带多重布尔约束的成本最小化问题：给定一个成本数组 cost 和两个二元兼容性标识数组 compatible1 与 compatible2，要求选出一组下标，使得这些下标在 compatible1 中对应值为 1 的个数 ≥ min_compatible，同时在 compatible2 中也为 1 的个数也 ≥ min_compatible，且所选下标的 cost 总和最小。
该问题虽与经典背包问题形式不同（无容量限制，但有双重计数约束），但因其规模通常不大（如题目中仅 5 个元素），采用穷举所有可行子集是合理且可验证最优性的策略。Python 标准库 itertools.combinations 提供了高效生成指定长度子集的能力，我们只需遍历从 min_compatible 到 n 的所有可能选取数量，并对每个组合检查双重约束是否满足。
以下是完整可运行的解决方案：
from itertools import combinations
from typing import Optional
def get_min_cost(
cost: list[int],
compatible1: list[int],
compatible2: list[int],
min_compatible: int
) -> Optional[int]:
n = len(cost)
min_cost = None
# 尝试选取 k 个元素，k 从 min_compatible 到全部 n 个
for k in range(min_compatible, n + 1):
for indices in combinations(range(n), k):
# 统计当前组合在两个兼容数组中满足条件的个数
c1_count = sum(compatible1[i] for i in indices)
c2_count = sum(compatible2[i] for i in indices)
total_cost = sum(cost[i] for i in indices)
# 同时满足两个约束才更新最小成本
if c1_count >= min_compatible and c2_count >= min_compatible:
min_cost = min(min_cost, total_cost) if min_cost is not None else total_cost
return min_cost
# 示例调用
result = get_min_cost(
cost=[2, 3, 1, 6, 4],
compatible1=[1, 1, 0, 1, 0],
compatible2=[0, 1, 0, 0, 1],
min_compatible=2
)
print(result) # 输出：9✅ 关键说明：
- 答案
9对应选取索引0, 1, 4（注意：原题描述中“index 5”为笔误，因数组长度为 5，合法索引为0–4；实际最优解为索引0,1,4→ cost[0]+cost[1]+cost[4] = 2+3+4 = 9），此时compatible1[0]=1, compatible1[1]=1, compatible1[4]=0→ 共 2 个；compatible2[0]=0, compatible2[1]=1, compatible2[4]=1→ 同样共 2 个，完全满足约束。 - 时间复杂度为 O(2ⁿ·n)，适合
n ≤ 20；若n更大，需转向动态规划或整数线性规划（如用PuLP或ortools）建模求解。 - 本方法保证全局最优，无贪心偏差——避免了“先取公共高兼容项再补差”的启发式策略可能遗漏更优组合的风险。
总结：当问题规模可控时，组合枚举是最直观、最可靠的起点；它既是验证其他启发式算法正确性的基准，也是教学和原型开发中的首选方案。
