Final integrative check — 0/1 knapsack DP with reconstruction (the OilKnapsack shape): print the max value and the chosen items.

Answer

def knapsack(weights, values, W): n = len(weights) dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): wi, vi = weights[i - 1], values[i - 1] for w in range(W + 1): dp[i][w] = dp[i - 1][w] if wi <= w and dp[i - 1][w - wi] + vi > dp[i][w]: dp[i][w] = dp[i - 1][w - wi] + vi # reconstruct chosen, w = [], W for i in range(n, 0, -1): if dp[i][w] != dp[i - 1][w]: chosen.append(i - 1) w -= weights[i - 1] chosen.reverse() return dp[n][W], chosen weights = [1, 3, 4, 5] values = [1, 4, 5, 7] best, items = knapsack(weights, values, 7) print("max value:", best) print("chosen items (0-indexed):", items)