Python实现带数量与类别约束的背包问题求解（啤酒选购场景）

我们使用OR-Tools整数规划工具求解，无需手动实现复杂的动态规划逻辑，对大规模数据集的处理性能远优于暴力枚举方案。

前置安装 #

首先安装依赖库：

pip install ortools

完整可运行代码 #

from ortools.linear_solver import pywraplp

# 输入参数
capacity = 6
max_money = 20
beers = [ 
  {"name":"Beer1",  "type":"Lager",   "price":3.50, "score":4.1},
  {"name":"Beer2",  "type":"Porter",  "price":4.90, "score":4.5},
  {"name":"Beer3",  "type":"IPA",     "price":3.70, "score":4.0},
  {"name":"Beer4",  "type":"Stout",   "price":3.20, "score":4.2},
  {"name":"Beer5",  "type":"Amber",   "price":3.80, "score":3.9},
  {"name":"Beer6",  "type":"Stout",   "price":2.70, "score":2.9},
  {"name":"Beer7",  "type":"IPA",     "price":2.50, "score":3.2},
  {"name":"Beer8",  "type":"Pilsner", "price":3.10, "score":4.0},
  {"name":"Beer9",  "type":"Amber",   "price":3.00, "score":4.1},
  {"name":"Beer10", "type":"Porter",  "price":2.80, "score":3.3},
  {"name":"Beer11", "type":"IPA",     "price":3.70, "score":4.0},
  {"name":"Beer12", "type":"Lager",   "price":3.20, "score":4.2},
  {"name":"Beer13", "type":"Amber",   "price":3.30, "score":3.5},
  {"name":"Beer14", "type":"Stout",   "price":2.90, "score":2.8},
  {"name":"Beer15", "type":"Lager",   "price":3.20, "score":4.2},
]

# 初始化求解器
solver = pywraplp.Solver.CreateSolver('SCIP')
if not solver:
    raise Exception("SCIP solver not available")

# 定义变量：x[i] = 1 代表选中第i款啤酒，0代表未选中
x = {}
for i in range(len(beers)):
    x[i] = solver.IntVar(0, 1, f'x_{i}')

# 约束1：恰好选6瓶
solver.Add(solver.Sum(x[i] for i in range(len(beers))) == capacity)

# 约束2：总花费小于20美元，为避免浮点误差价格转成整数（*10）
solver.Add(solver.Sum(x[i] * int(beers[i]['price'] * 10) for i in range(len(beers))) < int(max_money * 10))

# 约束3：恰好2瓶Lager
solver.Add(solver.Sum(x[i] for i in range(len(beers)) if beers[i]['type'] == 'Lager') == 2)

# 约束4：恰好1瓶Stout
solver.Add(solver.Sum(x[i] for i in range(len(beers)) if beers[i]['type'] == 'Stout') == 1)

# 约束5：恰好1瓶Amber
solver.Add(solver.Sum(x[i] for i in range(len(beers)) if beers[i]['type'] == 'Amber') == 1)

# 优化目标：最大化总评分
solver.Maximize(solver.Sum(x[i] * beers[i]['score'] for i in range(len(beers))))

# 求解
status = solver.Solve()

# 输出结果
if status == pywraplp.Solver.OPTIMAL:
    selected = [beers[i]['name'] for i in range(len(beers)) if x[i].solution_value() > 0.5]
    total_price = sum(beers[i]['price'] for i in range(len(beers)) if x[i].solution_value() > 0.5)
    total_score = sum(beers[i]['score'] for i in range(len(beers)) if x[i].solution_value() > 0.5)
    print("选中的啤酒：", selected)
    print("总花费：", round(total_price, 2), "美元")
    print("总评分：", round(total_score, 2))
else:
    print("没有符合条件的组合")

方案说明 #

• 天然满足所有啤酒不重复的要求：每款啤酒对应独有的0-1变量，最多被选中1次
• 性能表现：即便是数千款啤酒的数据集，也能在毫秒级完成求解，远快于暴力枚举方案
• 可扩展性强：如果后续要新增约束（比如最多选1瓶IPA、某款酒必须选/不能选），只需要新增对应的约束规则即可，无需修改核心逻辑

示例数据运行输出 #

选中的啤酒： ['Beer3', 'Beer4', 'Beer8', 'Beer9', 'Beer12', 'Beer15']
总花费： 19.9 美元
总评分： 24.7

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