基于Python PuLP的带距离约束物品最优组合选取 实现评分最大化

已知输入数组distance为距起点的升序距离序列，rating为对应物品的评分，需要满足指定约束求解总评分最大的5个物品组合。

需求约束 #

• 目标：总rating取最大值
• 相邻选取物品的distance差值不超过360
• 总distance达到指定阈值
• 仅可选取5个物品

完整实现代码 #

from pulp import LpProblem, LpMaximize, LpVariable, lpSum, LpStatus, value

# 输入参数
distance = [12, 326, 347, 359, 553, 590, 687, 1007, 1008, 1321, 1360, 1411]
rating = [4.3, 4.8, 2.7, 2.6, 3.6, 0.8, 4.4, 2.8, 2.6, 2.1, 2.8, 3.3]
max_to_pick = 5  # 固定选5个物品
min_total_distance = 1000  # 总distance阈值，可按需修改

# 初始化问题
prob = LpProblem("optimal_selection", LpMaximize)
n = len(distance)
N = range(n)
# 二进制变量x[i]=1表示选中第i个物品
x = LpVariable.dicts('x', N, cat="Binary")

# 目标函数：最大化总评分
prob += lpSum([rating[i]*x[i] for i in N])

# 约束1：恰好选5个物品
prob += lpSum([x[i] for i in N]) == max_to_pick

# 约束2：总distance不低于指定阈值
prob += lpSum([x[i]*distance[i] for i in N]) >= min_total_distance

# 约束3：相邻选中物品的distance差值不超过360
for i in N:
    for j in range(i+1, n):
        if distance[j] - distance[i] > 360:
            # 若i和j都被选中，则中间必须至少有一个选中的物品
            prob += x[i] + x[j] - lpSum([x[m] for m in range(i+1, j)]) <= 1

# 求解
prob.solve()
print("求解状态:", LpStatus[prob.status])
print("最大总评分:", round(value(prob.objective), 2))
selected_idx = [i for i in N if value(x[i]) == 1]
print("选中的物品索引:", selected_idx)
print("对应distance:", [distance[i] for i in selected_idx])
print("对应rating:", [rating[i] for i in selected_idx])

约束说明 #

• 选点数量约束用==代替<=，满足恰好选5个的要求
• 相邻距离约束的逻辑是：只要两个点的距离差超过360，就不能同时作为相邻选中点出现，必须中间有其他选中点间隔
• 可根据实际需求修改min_total_distance参数调整总distance阈值

内容的提问来源于stack exchange，提问作者eater of rice