如何修改0-1背包动态规划Python代码以返回最优子集元素？

没问题！要拿到最优子集的具体元素，我们只需要在构建完动态规划表之后，回溯这个表来找出哪些物品被选中了。我来帮你修改代码，并且一步步解释怎么做。

修改后的完整代码 #

def knapSack(W, wt, val, n):
    # 创建DP表，K[i][w]表示前i个物品在容量w下的最大价值
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    
    # 构建DP表（补全了你原来未完成的逻辑）
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    
    # 回溯找出选中的物品
    max_value = K[n][W]
    remaining_weight = W
    selected_items = []
    
    for i in range(n, 0, -1):
        # 如果当前物品的加入改变了最大价值，说明它被选中了
        if max_value != K[i-1][remaining_weight]:
            selected_items.append(i-1)  # 存储物品的原始索引（从0开始）
            max_value -= val[i-1]
            remaining_weight -= wt[i-1]
        if max_value == 0:
            break  # 价值归0，无需继续回溯
    
    # 返回总价值和选中的物品索引列表
    return K[n][W], selected_items

关键逻辑解释 #

1. DP表构建 #

这部分和你原来的思路一致：

• K[i][w]代表前i个物品，在背包容量为w时能获得的最大价值。
• 当第i个物品的重量wt[i-1]小于等于当前容量w时，我们选择拿或不拿这个物品中价值更大的选项；否则只能不拿。

2. 回溯找最优子集 #

回溯的核心思路是从DP表的右下角（K[n][W]，即所有物品都考虑、容量拉满的情况）倒推：

• 如果K[i][remaining_weight]不等于K[i-1][remaining_weight]，说明第i个物品（对应原始列表的索引i-1）被包含在最优解中——因为拿了它之后，总价值比不拿它时更高。
• 每次确认选中一个物品后，我们就把它的索引加入列表，同时减去它的价值和剩余容量，继续往前检查前面的物品。
• 当剩余价值为0时，可以提前终止回溯，因为已经找全了所有贡献价值的物品。

测试示例 #

# 测试数据
W = 50
wt = [10, 20, 30]
val = [60, 100, 120]
n = len(wt)

# 调用函数
total_value, selected_indices = knapSack(W, wt, val, n)

# 输出结果
print(f"最优总价值: {total_value}")
print(f"选中物品的索引: {selected_indices}")
print(f"选中物品的重量: {[wt[idx] for idx in selected_indices]}")
print(f"选中物品的价值: {[val[idx] for idx in selected_indices]}")

输出结果：

最优总价值: 220
选中物品的索引: [1, 2]
选中物品的重量: [20, 30]
选中物品的价值: [100, 120]

这个结果符合预期：容量50的背包，选重量20和30的物品，总价值220是最优解。

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