0-1背包问题：如何从DP表中获取Top-K高利润解决方案

原有的动态规划方法只能得到单个最优解，核心原因是DP表仅存储了每个状态下的最大价值，丢失了达到该价值的多条路径信息。要获取Top-K解，有两种高效的思路：

一、改进DP表，存储每个状态的Top-K候选解 #

把DP表的每个元素从单一整数，改成一个有序列表，存储不超过K个**（总价值，物品索引集合）**的元组，始终保持列表按总价值降序排列，并且剔除重复的解。

实现思路 #

1. 初始化DP表：dp[i][w] 表示考虑前i个物品、背包容量为w时的Top-K候选解列表。
2. 状态转移：
   • 不选第i个物品：直接继承dp[i-1][w]的候选解
   • 选第i个物品：如果当前物品重量≤w，就把dp[i-1][w-weights[i]]的每个解加上当前物品的价值和索引，得到新的候选解
   • 合并上述两类候选解，去重后按价值降序排序，保留前K个解作为dp[i][w]的内容
3. 最终从dp[n][capacity]及所有容量≤capacity的状态中提取候选解，去重排序后取Top-K（含并列解）

代码示例（针对你的输入） #

import numpy as np

def knapsack_top_k(weights, values, capacity, k):
    n = len(weights)
    # 初始化DP表：每个位置是一个列表，存储(总价值, 物品索引集合)
    dp = [[[] for _ in range(capacity+1)] for _ in range(n+1)]
    # 初始状态：0物品0容量的解
    dp[0][0] = [(0, set())]
    
    for i in range(1, n+1):
        w_i = weights[i-1]
        v_i = values[i-1]
        for w in range(capacity+1):
            # 不选当前物品的候选解
            candidates = dp[i-1][w].copy()
            # 选当前物品的候选解
            if w >= w_i:
                for val, items in dp[i-1][w - w_i]:
                    new_val = val + v_i
                    new_items = items.copy()
                    new_items.add(i-1)  # 原物品是零基索引
                    candidates.append((new_val, new_items))
            
            # 去重：相同价值+相同物品集合的只留一个
            unique_candidates = {}
            for val, items in candidates:
                key = (val, frozenset(items))
                if key not in unique_candidates:
                    unique_candidates[key] = (val, items)
            candidates = list(unique_candidates.values())
            
            # 按价值降序排序，取前k个
            candidates.sort(key=lambda x: -x[0])
            dp[i][w] = candidates[:k]
    
    # 收集所有容量≤capacity的解，再排序取Top-K
    all_candidates = []
    for w in range(capacity+1):
        all_candidates.extend(dp[n][w])
    # 去重后排序
    unique_all = {}
    for val, items in all_candidates:
        key = (val, frozenset(items))
        if key not in unique_all:
            unique_all[key] = (val, sorted(items))
    sorted_results = sorted(unique_all.values(), key=lambda x: -x[0])
    return sorted_results[:k]

# 你的输入示例
weights = [1, 2, 3, 2, 2]
values = [6, 10, 12, 6, 5]
capacity = 5
k = 3

top_k = knapsack_top_k(weights, values, capacity, k)
# 输出结果
print("Top-K解：")
for val, items in top_k:
    print(f"总价值：{val}，物品（零基索引）：{', '.join(map(str, items))}")

运行后会输出与你示例一致的结果，若存在更多并列最优解，会全部保留后再取前K个。

二、基于原DP表的回溯剪枝搜索 #

如果不想修改原DP表结构，可以基于原有最大价值DP表，通过回溯+剪枝枚举所有可能的解，筛选出Top-K结果。

实现思路 #

1. 预计算每个位置之后的物品最大价值和（用于剪枝）
2. 从最后一个物品开始回溯，每次分两种情况：选当前物品（重量允许时）和不选当前物品
3. 剪枝条件：如果当前已选价值 + 剩余物品最大价值和 < 已找到的第K个解的价值，停止该分支搜索
4. 记录所有合法解，最后按价值降序排序，取前K个（保留并列解）

代码示例 #

import numpy as np

def knapsack(weights, values, capacity):
    # 原DP表构建函数，保持不变
    n = len(weights)
    weights = np.concatenate(([0], weights))
    values = np.concatenate(([0], values))
    
    table = np.zeros((n+1, capacity+1), dtype=np.int64)
    for i in range(n+1):
        for w in range(capacity+1):
            if i == 0 or w == 0:
                table[i, w] = 0
            elif weights[i] <= w:
                table[i, w] = max(
                    table[i-1, w-weights[i]] + values[i],
                    table[i-1, w]
                )
            else:
                table[i, w] = table[i-1, w]
    return table

def get_top_k_items(weights, values, capacity, table, k):
    n = len(weights)
    # 预计算后缀最大价值和：suffix_max[i]表示第i到n-1个物品的最大价值和
    suffix_max = [0]*(n+1)
    for i in range(n-1, -1, -1):
        suffix_max[i] = suffix_max[i+1] + values[i]
    
    solutions = set()
    current_val = 0
    current_items = []
    
    def backtrack(i, remaining_cap):
        nonlocal current_val
        # 剪枝：当前可能的最大价值小于已有的第K个解，直接返回
        if len(solutions) >= k and current_val + suffix_max[i] <= sorted(solutions, reverse=True)[k-1][0]:
            return
        if i == 0:
            if current_val > 0:
                solutions.add((current_val, frozenset(current_items.copy())))
            return
        # 不选第i-1个物品（i从n开始，对应原零基索引i-1）
        backtrack(i-1, remaining_cap)
        # 选第i-1个物品
        w = weights[i-1]
        v = values[i-1]
        if remaining_cap >= w:
            current_val += v
            current_items.append(i-1)
            backtrack(i-1, remaining_cap - w)
            current_items.pop()
            current_val -= v
    
    backtrack(n, capacity)
    # 转换为排序后的列表
    sorted_solutions = sorted([(val, sorted(items)) for val, items in solutions], key=lambda x: -x[0])
    # 处理并列解：先保留所有最高价值解，再补全到K个
    result = []
    if not sorted_solutions:
        return result
    current_max_val = sorted_solutions[0][0]
    # 先加所有最高价值的解
    for sol in sorted_solutions:
        if sol[0] == current_max_val:
            result.append(sol)
        else:
            break
    # 如果还不够k个，加后面的解
    if len(result) < k:
        result.extend(sorted_solutions[len(result):k])
    return result

# 测试你的示例
weights = [1, 2, 3, 2, 2]
values = [6, 10, 12, 6, 5]
capacity = 5
k = 3

dp_table = knapsack(weights, values, capacity)
top_k = get_top_k_items(weights, values, capacity, dp_table, k)
print("Top-K解：")
for val, items in top_k:
    print(f"总价值：{val}，物品（零基索引）：{', '.join(map(str, items))}")

两种方法对比 #

• 改进DP表法：时间复杂度略高（每个状态需处理K个候选解），但能在DP过程中直接筛选最优候选解，适合K较小的场景。
• 回溯剪枝法：无需修改原DP表，利用剪枝减少搜索量，适合原DP表已存在、且K不是特别大的场景。

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