The knapsack problem is a classic optimization problem that perfectly demonstrates the power of dynamic programming. At its core, it asks: given limited capacity, how do you select items to maximize value?
Dynamic programming works by breaking complex problems into overlapping subproblems and storing their solutions. For the knapsack problem, the key insight is that for any item, you face a binary choice: include it or don't include it. The optimal solution depends on making the best choice at each step.
The magic happens when you realize that the problem has optimal substructure. If you know the optimal solution for a smaller knapsack (less capacity) and fewer items, you can build up to the optimal solution for larger problems. This is where the 2D table comes in - one dimension represents the items considered so far, the other represents the weight capacity.
The recurrence relation captures the essence: for each item and weight limit, the maximum value is either the best solution without this item, or the best solution that includes this item (if it fits). You take whichever is better.
What makes this approach efficient is memoization - storing results in the table means you never recalculate the same subproblem twice. Without this, you'd have exponential time complexity as you'd explore every possible combination. With dynamic programming, you achieve O(n*W) time complexity.
The beauty of the knapsack algorithm extends far beyond backpacks. It models resource allocation problems everywhere: CPU scheduling, memory management, investment portfolios, and even DNA sequence alignment in bioinformatics all use similar dynamic programming approaches.
1def coin_change(coins, amount):
2 """Find minimum coins needed to make amount (similar DP pattern)"""
3 # dp[i] = minimum coins needed for amount i
4 dp = [float('inf')] * (amount + 1)
5 dp[0] = 0 # Base case: 0 coins for amount 0
6
7 for coin in coins:
8 for i in range(coin, amount + 1):
9 # Choose: use this coin or don't use it
10 dp[i] = min(dp[i], dp[i - coin] + 1)
11
12 return dp[amount] if dp[amount] != float('inf') else -1