如何基于预算限制选取总价值最高的15个名称组合及前20个最优解

这个需求属于带基数约束的多解0-1背包问题：要求选择恰好15个物品（对应Name列），总成本≤200美元，总价值最高，同时返回前20组不重复的最优组合。

实现步骤 #

1. 数据预处理 #

首先把原始数据里的$符号去掉，转换为数值类型，Python示例代码如下：

import pandas as pd
# 读取数据集，可根据实际存储格式替换读取方式
df = pd.read_csv("你的数据集路径.csv")
# 把Value、Cost列的货币符号去掉，转成整数
df["Value"] = df["Value"].str.replace("$", "").astype(int)
df["Cost"] = df["Cost"].str.replace("$", "").astype(int)

2. 单组最优解求解 #

如果只需要1组总价值最高的组合，可以用动态规划实现，状态定义为dp[k][c]表示选k个物品、总成本为c时的最大总价值：

max_count = 15
max_total_cost = 200
# 初始化dp数组，-inf代表该状态不可达
dp = [[float("-inf")] * (max_total_cost + 1) for _ in range(max_count + 1)]
dp[0][0] = 0
# 辅助数组，用来回溯找到对应的Name组合
prev = [[None] * (max_total_cost + 1) for _ in range(max_count + 1)]

for idx, row in df.iterrows():
    name, val, cost = row["Name"], row["Value"], row["Cost"]
    # 倒序遍历避免重复选中同一个物品
    for k in range(max_count, 0, -1):
        for c in range(max_total_cost, cost - 1, -1):
            if dp[k-1][c - cost] + val > dp[k][c]:
                dp[k][c] = dp[k-1][c - cost] + val
                prev[k][c] = (idx, k-1, c - cost)

计算完成后在dp[15][c]里找c≤200的最大值，再回溯prev数组就能得到对应的15个Name。

3. 前20组最优解求解 #

如果需要返回前20组不重复的组合，可以用整数规划库直接求解，不用自己实现复杂的分支定界逻辑，用mip库的示例代码如下：

from mip import Model, xsum, maximize, BINARY

m = Model()
# 定义决策变量，x[i]=1代表选中第i行的Name
x = [m.add_var(var_type=BINARY) for i in range(len(df))]
# 目标函数：最大化总Value
m.objective = maximize(xsum(df["Value"][i] * x[i] for i in range(len(df))))
# 约束1：恰好选15个Name
m += xsum(x[i] for i in range(len(df))) == 15
# 约束2：总Cost不超过200
m += xsum(df["Cost"][i] * x[i] for i in range(len(df))) <= 200
# 设置返回前20个最优解
m.set_num_solutions(20)
m.optimize()

# 整理所有结果
result_list = []
for sol in m.get_solutions():
    selected_idx = [i for i in range(len(df)) if sol.x[i] > 0.5]
    selected_names = df.iloc[selected_idx]["Name"].tolist()
    total_val = sum(df["Value"][i] for i in selected_idx)
    total_cost = sum(df["Cost"][i] for i in selected_idx)
    result_list.append({
        "selected_names": selected_names,
        "total_value": total_val,
        "total_cost": total_cost
    })

补充说明 #

• 如果数据集规模很小（总Name数≤30），可以直接暴力枚举所有15个元素的组合，筛选符合约束的后按总Value排序取前20，实现更简单
• 如果数据集规模很大（总Name数>100），建议用遗传算法、模拟退火等启发式算法近似求解，速度会比精确算法快很多

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