动态规划算法--01背包问题详细讲解步骤

举个例子

要确定哪些物品被放入背包以达到最大价值，可以在计算 dp 数组的同时记录选择的物品。具体来说，可以使用一个额外的数组来记录每个状态的选择情况。以下是一个详细的步骤和代码实现：

n = 3
W = 5
weights = [2, 1, 3]
values = [6, 3, 5]

初始化 dp 和 choice 数组

dp = [[0] * (W + 1) for _ in range(n + 1)]
choice = [[0] * (W + 1) for _ in range(n + 1)]print("初始状态:")
print("dp:")
for row in dp:print(row)
print("choice:")
for row in choice:print(row)

初始状态:

第1个物品（重量2，价值6）

# 第1个物品
for j in range(1, W + 1):if j >= weights[0]:if dp[0][j] < dp[0][j - weights[0]] + values[0]:dp[1][j] = dp[0][j - weights[0]] + values[0]choice[1][j] = 1else:dp[1][j] = dp[0][j]else:dp[1][j] = dp[0][j]print("处理第1个物品后:")
print("dp:")
for row in dp:print(row)
print("choice:")
for row in choice:print(row)

第2个物品（重量1，价值3）

# 第2个物品
for j in range(1, W + 1):if j >= weights[1]:if dp[1][j] < dp[1][j - weights[1