题目
设背包的载重M=6，有3件待载入物品，其重量分别为(w0,w1,w2) =(2,3,4),它们的价值分别为(p0,p1,p2) =(1,2,5)。求物品的最佳装载方案，使背包容纳物品的价值最高。
设背包的载重M=6，有3件待载入物品，其重量分别为(w0,w1,w2) =(2,3,4),它们的价值分别为(p0,p1,p2) =(1,2,5)。求物品的最佳装载方案，使背包容纳物品的价值最高。
题目解答
答案
回溯找出最佳装载方案：
chosen_items = []
j = M
for i in range(n, 0, -1):
if dp[i][j] != dp[i - 1][j]:
chosen_items.append(i - 1) # i-1 是物品的索引
j -= W[i - 1]
最大价值: dp[n][M]
选择的物品: chosen_items
根据上述步骤计算得出：
最大价值：( dp[3][6] ) = 6
选择的物品：选择的物品为物品0和物品1（索引从0开始），即重量为2和3的物品，价值分别为1和2。
最佳装载方案：
物品0: 重量2, 价值1
物品1: 重量3, 价值2
综上所述，最大价值为 6 ，最佳装载方案为选择物品 0 和 1。
解析
步骤 1：定义问题
问题是一个经典的0-1背包问题，其中背包的容量为M=6，有3件物品，每件物品有重量和价值。目标是选择物品，使得总价值最大，同时不超过背包的容量。
步骤 2：初始化动态规划表
创建一个二维数组dp，其中dp[i][j]表示前i个物品在容量为j时的最大价值。初始化dp[0][j] = 0，因为没有物品时，价值为0。
步骤 3：填充动态规划表
对于每个物品i，从1到n，以及每个容量j，从0到M，更新dp[i][j]。如果当前物品的重量大于容量j，则dp[i][j] = dp[i-1][j]，否则dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + p[i-1])。
步骤 4：回溯找出最佳装载方案
从dp[n][M]开始，回溯找出选择的物品。如果dp[i][j] != dp[i-1][j]，则物品i-1被选择，更新j -= w[i-1]。
问题是一个经典的0-1背包问题，其中背包的容量为M=6，有3件物品，每件物品有重量和价值。目标是选择物品，使得总价值最大，同时不超过背包的容量。
步骤 2：初始化动态规划表
创建一个二维数组dp，其中dp[i][j]表示前i个物品在容量为j时的最大价值。初始化dp[0][j] = 0，因为没有物品时，价值为0。
步骤 3：填充动态规划表
对于每个物品i，从1到n，以及每个容量j，从0到M，更新dp[i][j]。如果当前物品的重量大于容量j，则dp[i][j] = dp[i-1][j]，否则dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + p[i-1])。
步骤 4：回溯找出最佳装载方案
从dp[n][M]开始，回溯找出选择的物品。如果dp[i][j] != dp[i-1][j]，则物品i-1被选择，更新j -= w[i-1]。