What is the formula for 0-1 knapsack?

The 0-1 Knapsack Problem is one of the most classic and well-known problems in computer science and optimization. It is a dynamic programming example where the objective is to determine the most valuable subset of items to include in a knapsack, given a constraint on the total weight the knapsack can carry. This problem has significant practical applications — from resource allocation to budgeting — and serves as a cornerstone in understanding computational efficiency and optimization techniques.

In the 0-1 Knapsack Problem, each item has a weight and a value. The goal is to maximize the sum of the values of the items selected without exceeding the knapsack’s capacity. The “0-1” part refers to the condition that each item can either be taken (1) or not taken (0), meaning you cannot take a fraction of an item nor take the same item multiple times.

The Mathematical Formula

The 0-1 knapsack problem is usually expressed using a dynamic programming formula that builds an optimal solution progressively. Suppose:

• n is the number of items
• W is the maximum weight the knapsack can carry
• w[i] is the weight of the i-th item
• v[i] is the value of the i-th item
• dp[i][j] represents the maximum value that can be obtained by choosing from the first i items when the available capacity is j

The recurrence relation for the 0-1 Knapsack Problem is as follows:

if w[i] > j:
    dp[i][j] = dp[i-1][j]
else:
    dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

This recurrence states that if the item’s weight is more than the current capacity j, we cannot include it. So, the best we can do is to carry forward the previous value without including this item. Otherwise, we check two scenarios — one where we include the item and one where we don’t — and take the maximum result.

Tabular or Bottom-Up Implementation

Using a 2D table to store subproblem results, we fill the table row by row. The dimensions will be (n+1) x (W+1). The table is initialized with zeros in the beginning.

Here’s a sample structure for building the solution:

for i in range(1, n+1):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

Once the table is filled, the bottom-right cell will contain the maximum value that can be obtained within the given weight limit — i.e., dp[n][W].

Optimizing Space

The standard implementation uses O(nW) space. However, this can be optimized to O(W) by using a 1D array and updating it in reverse to ensure the dependencies from the previous iteration are maintained.

Here’s a basic concept of space optimization:

dp = [0 for j in range(W+1)]
for i in range(1, n+1):
    for j in range(W, w[i]-1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

This method dramatically reduces memory usage, especially crucial in real-time systems or memory-constrained environments.

Frequently Asked Questions (FAQ)

• Q: What is the difference between 0-1 Knapsack and Fractional Knapsack?
  A: In 0-1 Knapsack, an item can either be included fully or not at all. In Fractional Knapsack, items can be broken into smaller parts, and fractions can be taken to maximize value.
• Q: Can the 0-1 Knapsack be solved using recursion?
  A: Yes, but it is inefficient without memoization due to repeated computations. It is better solved using Dynamic Programming.
• Q: What is the time complexity of the dynamic programming solution?
  A: The basic dynamic programming approach has a time complexity of O(nW), where n is the number of items and W is the knapsack capacity.
• Q: Is it possible to retrieve the selected items after solving?
  A: Yes. By tracing back the DP table from dp[n][W], one can determine which items are included in the optimal solution.