如何用Python OR-Tools实现固定大小卡组的组合数最大化？

你的需求可以通过OR-Tools的CP-SAT求解器实现，但需要调整代码逻辑——OR-Tools不支持直接将逻辑表达式（如And）加入目标函数，必须通过辅助布尔变量标记每个组合是否被满足，再最大化这些变量的总和。

完整实现代码 #

from ortools.sat.python import cp_model

# 初始化CP-SAT模型与求解器
model = cp_model.CpModel()
solver = cp_model.CpSolver()

# 定义卡牌布尔变量：True代表选中该卡牌
cards = [
    model.NewBoolVar("card1"),
    model.NewBoolVar("card2"),
    model.NewBoolVar("card3"),
    model.NewBoolVar("card4")
]

# 定义所有卡牌组合
combos = [
    [cards[0], cards[1]],
    [cards[0], cards[2]],
    [cards[1], cards[3]],
    [cards[0], cards[2], cards[3]]
]

DECKSIZE = 3
# 添加约束：选中的卡牌数量必须等于DECKSIZE
model.Add(sum(cards) == DECKSIZE)

# 为每个组合创建辅助变量，标记该组合是否被完全满足
combo_vars = []
for idx, combo in enumerate(combos):
    combo_var = model.NewBoolVar(f"combo_{idx+1}")
    # 约束逻辑：只有当组合内所有卡牌都被选中时，辅助变量才为True
    model.AddBoolAnd(combo).OnlyEnforceIf(combo_var)
    model.AddImplication(combo_var, model.AddBoolAnd(combo))
    combo_vars.append(combo_var)

# 设置目标：最大化满足的组合数量
model.Maximize(sum(combo_vars))

# 求解并输出结果
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    print("选中的卡牌：")
    for card in cards:
        if solver.Value(card):
            print(f"- {card.Name()}")
    print(f"\n满足的组合总数：{int(solver.ObjectiveValue())}")
    print("满足的组合详情：")
    for idx, var in enumerate(combo_vars):
        if solver.Value(var):
            card_names = [card.Name() for card in combos[idx]]
            print(f"- 组合{idx+1}: {', '.join(card_names)}")
else:
    print("未找到最优解")

关键逻辑说明 #

1. 辅助变量的作用：OR-Tools的目标函数仅支持线性变量求和，无法直接处理And这类逻辑判断，因此用辅助变量映射每个组合的满足状态。
2. 约束绑定：通过AddBoolAnd和AddImplication确保辅助变量与组合的选中状态完全绑定——组合内所有卡牌都被选中时，辅助变量才为1，反之亦然。
3. 求解结果：运行后会输出选中的卡牌、满足的组合数量及具体组合，符合你要求的最大化组合数目标。

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