动态规划算法--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] = 1
else:
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