weights = [2,3,4,5]
values = [1,2,5,6]
capacity = 8
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# Build DP table
for i in range(1, n + 1): #row
for w in range(1, capacity + 1): #column
if weights[i – 1] <= w:
dp[i][w] = max(values[i – 1] + dp[i – 1][w – weights[i – 1]], dp[i – 1][w])
else:
dp[i][w] = dp[i – 1][w]
# Backtrack to find selected items
w = capacity
selected = []
for i in range(n, 0, -1): #reverse order from 8 ex.
if dp[i][w] != dp[i – 1][w]: #upar wala element usi column ka
selected.append(i – 1)
w -= weights[i – 1]
selected.reverse()
return dp[n][capacity], selected
max_value, selected_items = knapsack_01(weights, values, capacity)
print(“Maximum Value:”, max_value)
print(“Selected Items (index):”, selected_items)