Knapsack & subset-sum

Choosing the optimal combination of items under a strict capacity constraint.

The idea

The 0/1 Knapsack Problem gives you a bag with weight capacity W, and a list of items each with a weight and a value. You want to maximise the total value without busting the weight.

For every item, you have a choice: Skip it (carry over the max value for this capacity from previous items) or Take it (add its value to the max value of capacity - item.weight from previous items). The DP grid tracks dp[item][capacity].

Max Capacity: 5 | Items: A(w2,v3), B(w3,v4), C(w4,v5)

Empty grid. Rows = Items, Cols = Capacity 0 to 5.

How it works (2D Array)

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                # Take or Skip
                dp[i][w] = max(
                    dp[i-1][w], 
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
            else:
                # Skip
                dp[i][w] = dp[i-1][w]
                
    return dp[n][W]