0/1 Knapsack Problem

The 0/1 Knapsack problem asks: given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, determine the maximum total value that can be carried, where each item can either be fully included or excluded (no fractional items).

Recursive Approach

At every item, decide to either include it (if it fits) or skip it, and take the maximum of both choices. This naive recursion recomputes overlapping subproblems and runs in exponential time.

Dynamic Programming Approach

Build a table dp[i][w] representing the maximum value achievable using the first i items with capacity w. Each cell is computed from smaller subproblems, avoiding recomputation.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w],
                                dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))  # Output: 9

Complexity

Applications

• Resource allocation and budgeting problems.
• Cargo loading and shipment optimization.
• Portfolio selection under a fixed investment budget.