物品：(重量, 价值) items = [(2, 6), (2, 10), (3, 12), (6, 20)] W = 10 n = len(items) dp[i][j] = 前i个物品，背包容量j时的最大价值 dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): w, v = items[i - 1] for j in range(1, W + 1): if j >= w: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) else: dp[i][j] = dp[i - 1][j] 回溯找选了哪些物品 selected = [] j = W for i in range(n, 0, -1): if dp[i][j] != dp[i - 1][j]: selected.append(i) j -= items[i - 1][0] selected.sort() print("最大价值:", dp[n][W]) print("选中物品编号:", selected)