Knapsack via Dynamic Programming

Fill the 0/1 knapsack table for four items and a small capacity, then backtrack to recover which items the optimum selects.

Problem

The 0/1 knapsack problem asks which subset of items, each with a weight and value, maximizes total value without exceeding a capacity. Dynamic programming solves it in pseudo-polynomial time by building a table indexed by item count and remaining capacity.

Items

Four items with (weight, value): (1,1), (3,4), (4,5), (5,7), and capacity W=7. The recurrence is dp[i][w] = max(dp[i-1][w], value_i + dp[i-1][w - weight_i]) when the item fits.

w=[1,3,4,5]; v=[1,4,5,7]; W=7; n=4
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    for c in range(W+1):
        dp[i][c]=dp[i-1][c]
        if w[i-1]<=c:
            dp[i][c]=max(dp[i][c], v[i-1]+dp[i-1][c-w[i-1]])
print('best value',dp[n][W])  # 9
# backtrack
c=W; take=[]
for i in range(n,0,-1):
    if dp[i][c]!=dp[i-1][c]:
        take.append(i-1); c-=w[i-1]
print('items',sorted(take))  # 1 and 2 -> (3,4)+(4,5)=9

Result

The optimum is value 9, achieved by taking items (3,4) and (4,5), which fill weight 7 exactly. Backtracking compares each cell to the row above: a difference means the item was included. A greedy value-per-weight heuristic would pick item (5,7) first and get stuck at 8, showing why exact DP matters here.

• Runtime is O(n W), efficient only when capacity is modest; large W needs approximation or branch-and-bound.
• The table stores optimal sub-solutions so overlapping subproblems are solved once.
• This same allocate-under-constraint structure appears in Kronos scheduling of limited test-stand time across experiments.