预算约束下筛选15个最高总价值条目及Top20最优组合方案查询

问题梳理 #

本次需求如下：

• 从含Name、Value、Cost三个字段的数据集里，恰好选15个不重复的Name
• 硬性约束：所有选中项的总花费不超过200美元
• 核心目标：满足约束的前提下总Value最高
• 额外需求：输出总Value排名前20的互不重复的15项组合

提供的示例数据集整理如下：

实现思路 #

这个需求属于固定项数的0-1背包拓展问题，需要额外支持Top K最优解输出，具体实现逻辑如下：

1. 数据预处理：先把Value和Cost字段的$符号清除，转换为数值类型方便计算
2. 动态规划状态设计：用二维状态dp[count][cost]存储选count个物品、总花费为cost时的最大总Value，同时用一个三维列表path[count][cost]记录所有能达到这个最大值的物品选择路径
3. 状态转移：遍历每一个物品，从后往前更新状态（避免重复选同一个物品），每次更新时同步记录路径
4. Top20结果提取：遍历所有count=15、cost≤200的状态，收集所有对应路径，按总Value倒序排序后取前20个去重的组合即可

参考代码片段 #

import pandas as pd

# 数据预处理
df = pd.read_csv("你的数据集路径.csv") # 替换为你的实际数据集路径
df['Value'] = df['Value'].str.replace('$','').astype(int)
df['Cost'] = df['Cost'].str.replace('$','').astype(int)
items = df.to_dict('records')

max_cost = 200
select_count = 15
top_k = 20

# 初始化DP和路径存储：dp[选的数量][总花费] = 最大Value
dp = [[-float('inf')] * (max_cost + 1) for _ in range(select_count + 1)]
dp[0][0] = 0
# paths[选的数量][总花费] = 所有达到该最大值的物品索引列表
paths = [[[] for _ in range(max_cost + 1)] for __ in range(select_count + 1)]
paths[0][0] = [[]]

for idx, item in enumerate(items):
    val = item['Value']
    cost = item['Cost']
    # 倒序遍历避免重复选同一个物品
    for c in range(select_count, 0, -1):
        for j in range(max_cost, cost -1, -1):
            if dp[c-1][j - cost] + val > dp[c][j]:
                dp[c][j] = dp[c-1][j - cost] + val
                paths[c][j] = [p + [idx] for p in paths[c-1][j - cost]]
            elif dp[c-1][j - cost] + val == dp[c][j]:
                paths[c][j].extend([p + [idx] for p in paths[c-1][j - cost]])

# 收集所有符合条件的组合
all_valid = []
for j in range(max_cost + 1):
    if dp[select_count][j] == -float('inf'):
        continue
    for path in paths[select_count][j]:
        total_val = dp[select_count][j]
        # 转换为Name列表
        name_list = [items[i]['Name'] for i in path]
        all_valid.append((-total_val, name_list)) # 负号方便升序排序

# 去重+取前20
all_valid.sort()
res = []
seen = set()
for val_neg, names in all_valid:
    name_tuple = tuple(sorted(names))
    if name_tuple not in seen:
        seen.add(name_tuple)
        res.append((-val_neg, names))
        if len(res) >= top_k:
            break

# 输出结果
for rank, (total_val, name_list) in enumerate(res, 1):
    print(f"第{rank}名，总Value：${total_val}，选中名单：{name_list}")

注意事项 #

• 如果你的数据集规模很大（超过100条），可以优化路径存储逻辑避免内存占用过高，只存每个状态的前K个最优路径即可
• 若允许同一个Name被多次选中，把遍历顺序改为正序即可切换为完全背包逻辑

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