0/1 Knapsack Problem

1. Introduction

The Knapsack problem is one of the most studied combinatorial optimization problems in computer science. Imagine a thief breaking into a store with a knapsack that can carry at most W kilograms. The store has n items, each with a weight and a value. The thief must decide which items to take to maximize the total value without exceeding the weight capacity.

"The knapsack problem is the key to understanding many optimization problems in operations research and computer science. Its simplicity makes it an ideal teaching tool; its depth makes it an active area of research." -- Hans Kellerer, Knapsack Problems

In the 0/1 variant, each item is either taken entirely or left behind -- there is no option to take a fraction of an item. This constraint makes the problem NP-hard in general, but dynamic programming provides a pseudo-polynomial time solution.

2. Problem Definition

Input:n items, each with weight w[i] and value v[i], and a knapsack capacity W.

Output: The maximum total value achievable without exceeding capacity W.

With capacity W = 7, the optimal selection is Items 2 and 3 (weight = 3 + 4 = 7, value = 4 + 5 = 9).

3. Brute Force Approach

The brute force approach generates all 2^n subsets of items, computes the total weight and value for each, and returns the maximum value among subsets that fit within capacity.

functionknapsackBrute(w, v, n, W): if n == 0or W == 0: return0// If item n is too heavy, skip itif w[n-1] > W: returnknapsackBrute(w, v, n-1, W) // Take the max of including or excluding item n include = v[n-1] + knapsackBrute(w, v, n-1, W - w[n-1]) exclude = knapsackBrute(w, v, n-1, W) returnmax(include, exclude)

This generates an exponential number of recursive calls, with time complexity O(2^n).

4. Optimal Substructure

The 0/1 Knapsack problem has optimal substructure. Consider the last item (item n):

• If item n is in the optimal solution: The remaining items must form an optimal solution for capacity W - w[n] using items 1 through n-1.
• If item n is not in the optimal solution: The items must form an optimal solution for capacity W using items 1 through n-1.

The problem also has overlapping subproblems because different combinations of inclusion/exclusion decisions can lead to the same (item index, remaining capacity) state.

5. Recurrence Relation

Let dp[i][j] represent the maximum value achievable using items 1 through i with capacity j.

6. Top-Down (Memoization)

functionknapsackMemo(w, v, n, W, memo): if n == 0or W == 0: return0if memo[n][W] != -1: return memo[n][W] if w[n-1] > W: memo[n][W] = knapsackMemo(w, v, n-1, W, memo) else: include = v[n-1] + knapsackMemo(w, v, n-1, W - w[n-1], memo) exclude = knapsackMemo(w, v, n-1, W, memo) memo[n][W] = max(include, exclude) return memo[n][W]

7. Bottom-Up (Tabulation)

functionknapsackDP(w, v, n, W): dp = array[n+1][W+1], initialized to 0for i = 1to n: for j = 1to W: if w[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j - w[i-1]]) return dp[n][W]

8. Worked Example

Using the items from Section 2: weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity W = 7.

DP Table

The maximum value is dp[4][7] = 9. Let us trace how the table was filled for a key cell:

• dp[3][7]: Item 3 has weight 4, which fits in capacity 7. We compare dp[2][7] = 7 (exclude) with v[3] + dp[2][3] = 5 + 4 = 9 (include). Maximum is 9.
• dp[4][7]: Item 4 has weight 5, which fits. We compare dp[3][7] = 9 (exclude) with v[4] + dp[3][2] = 6 + 3 = 9 (include). Both equal 9, so we take 9.

9. Backtracking the Solution

To find which items were selected, we backtrack through the DP table starting from dp[n][W].

functionfindItems(dp, w, v, n, W): items = [] i = n, j = W while i > 0and j > 0: if dp[i][j] != dp[i-1][j]: // Item i was included items.append(i) j = j - w[i-1] i = i - 1return items

Backtracking Trace

Selected items: Item 2 (w=3, v=4) and Item 3 (w=4, v=5). Total weight = 7, total value = 9.

10. Complexity Analysis

11. Fractional Knapsack Variant

In the fractional knapsack, items can be divided into fractions. This version is solvable optimally with a greedy algorithm:

1. Compute the value-to-weight ratio v[i] / w[i] for each item.
2. Sort items by this ratio in descending order.
3. Greedily take items (or fractions of items) until the knapsack is full.

12. Applications

• Capital budgeting: Selecting investment projects with maximum return given limited capital.
• Cargo loading: Optimizing the selection of freight items for ships, trucks, or aircraft.
• Resource allocation: Distributing limited computational resources (CPU, memory) across tasks.
• Cutting stock problem: Minimizing material waste when cutting raw materials into specified sizes.
• Cryptography: The subset sum variant of knapsack is used in cryptographic systems.
• Portfolio optimization: Selecting assets with maximum expected return under risk and budget constraints.

13. References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms (4th ed.). MIT Press, 2022. Chapter 14: Dynamic Programming.
2. Kellerer, H., Pferschy, U., and Pisinger, D. Knapsack Problems. Springer, 2004.
3. Kleinberg, J. and Tardos, E. Algorithm Design. Pearson, 2005.
4. Martello, S. and Toth, P. Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.