6a:T895,def knapsack_memo(weights: list[int], values: list[int], capacity: int) -> int: """ Solve 0/1 Knapsack using top-down memoization. Args: weights: List of item weights values: List of item values (same length as weights) capacity: Maximum knapsack capacity Returns: Maximum value achievable without exceeding capacity """ n = len(weights) # Memoization cache: -1 indicates uncomputed # memo[i][c] = max value using items 0..i-1 with capacity c memo = [[-1] * (capacity + 1) for _ in range(n + 1)] def solve(item_index: int, remaining_capacity: int) -> int: """ Recursive helper with memoization. Args: item_index: Number of items to consider (1-indexed conceptually) remaining_capacity: Current available capacity Returns: Maximum value for this subproblem """ # Base case: no items left to consider if item_index == 0: return 0 # Base case: no capacity left if remaining_capacity == 0: return 0 # Check memo cache if memo[item_index][remaining_capacity] != -1: return memo[item_index][remaining_capacity] # Current item (0-indexed in our arrays) i = item_index - 1 weight_i = weights[i] value_i = values[i] # Case 1: Exclude current item exclude = solve(item_index - 1, remaining_capacity) # Case 2: Include current item (if it fits) include = 0 if weight_i <= remaining_capacity: include = value_i + solve(item_index - 1, remaining_capacity - weight_i) # Take maximum and cache result = max(exclude, include) memo[item_index][remaining_capacity] = result return result return solve(n, capacity) # Example usage if __name__ == "__main__": weights = [2, 1, 3, 2] values = [12, 10, 20, 15] capacity = 5 max_value = knapsack_memo(weights, values, capacity) print(f"Maximum value: {max_value}") # Output: 376b:T661,function knapsackMemo( weights: number[], values: number[], capacity: number ): number { /** * Solve 0/1 Knapsack using top-down memoization. */ const n = weights.length; // Memoization cache: Map for sparse access pattern const memo: Map = new Map(); function solve(itemIndex: number, remainingCapacity: number): number { // Base cases if (itemIndex === 0 || remainingCapacity === 0) { return 0; } // Create unique key for this subproblem const key = `${itemIndex},${remainingCapacity}`; // Check memo cache if (memo.has(key)) { return memo.get(key)!; } // Current item (0-indexed in our arrays) const i = itemIndex - 1; const weightI = weights[i]; const valueI = values[i]; // Case 1: Exclude current item const exclude = solve(itemIndex - 1, remainingCapacity); // Case 2: Include current item (if it fits) let include = 0; if (weightI <= remainingCapacity) { include = valueI + solve(itemIndex - 1, remainingCapacity - weightI); } // Take maximum and cache const result = Math.max(exclude, include); memo.set(key, result); return result; } return solve(n, capacity); } // Example usage const weights = [2, 1, 3, 2]; const values = [12, 10, 20, 15]; const capacity = 5; console.log(`Maximum value: ${knapsackMemo(weights, values, capacity)}`); // Output: Maximum value: 376c:T737,import java.util.HashMap; import java.util.Map; public class Knapsack { private int[] weights; private int[] values; private Map memo; public int knapsackMemo(int[] weights, int[] values, int capacity) { this.weights = weights; this.values = values; this.memo = new HashMap<>(); return solve(weights.length, capacity); } private int solve(int itemIndex, int remainingCapacity) { // Base cases if (itemIndex == 0 || remainingCapacity == 0) { return 0; } // Create unique key for this subproblem String key = itemIndex + "," + remainingCapacity; // Check memo cache if (memo.containsKey(key)) { return memo.get(key); } // Current item (0-indexed in our arrays) int i = itemIndex - 1; int weightI = weights[i]; int valueI = values[i]; // Case 1: Exclude current item int exclude = solve(itemIndex - 1, remainingCapacity); // Case 2: Include current item (if it fits) int include = 0; if (weightI <= remainingCapacity) { include = valueI + solve(itemIndex - 1, remainingCapacity - weightI); } // Take maximum and cache int result = Math.max(exclude, include); memo.put(key, result); return result; } public static void main(String[] args) { Knapsack solver = new Knapsack(); int[] weights = {2, 1, 3, 2}; int[] values = {12, 10, 20, 15}; int capacity = 5; int maxValue = solver.knapsackMemo(weights, values, capacity); System.out.println("Maximum value: " + maxValue); // Output: Maximum value: 37 } }6d:T8ce,def knapsack_tabulation(weights: list[int], values: list[int], capacity: int) -> int: """ Solve 0/1 Knapsack using bottom-up tabulation. Args: weights: List of item weights values: List of item values (same length as weights) capacity: Maximum knapsack capacity Returns: Maximum value achievable without exceeding capacity """ n = len(weights) # Create DP table # dp[i][c] = max value using items 0..i-1 with capacity c dp = [[0] * (capacity + 1) for _ in range(n + 1)] # Base case: dp[0][c] = 0 for all c (already initialized to 0) # Fill the table row by row for i in range(1, n + 1): # Current item (0-indexed in arrays) weight_i = weights[i - 1] value_i = values[i - 1] for c in range(capacity + 1): # Case 1: Exclude current item dp[i][c] = dp[i - 1][c] # Case 2: Include current item (if it fits) if weight_i <= c: include_value = dp[i - 1][c - weight_i] + value_i dp[i][c] = max(dp[i][c], include_value) return dp[n][capacity] # Visualization helper def knapsack_with_table(weights: list[int], values: list[int], capacity: int): """Returns both the max value and the complete DP table for visualization.""" n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): weight_i = weights[i - 1] value_i = values[i - 1] for c in range(capacity + 1): dp[i][c] = dp[i - 1][c] if weight_i <= c: dp[i][c] = max(dp[i][c], dp[i - 1][c - weight_i] + value_i) return dp[n][capacity], dp # Example with table visualization if __name__ == "__main__": weights = [2, 1, 3, 2] values = [12, 10, 20, 15] capacity = 5 max_value, table = knapsack_with_table(weights, values, capacity) print("DP Table:") print(" ", " ".join(f"c={c}" for c in range(capacity + 1))) for i, row in enumerate(table): item_info = f"Item {i}" if i > 0 else "No items" print(f"{item_info:9}", row) print(f" Maximum value: {max_value}")6e:T4e0,function knapsackTabulation( weights: number[], values: number[], capacity: number ): number { /** * Solve 0/1 Knapsack using bottom-up tabulation. */ const n = weights.length; // Create DP table: dp[i][c] = max value using items 0..i-1 with capacity c const dp: number[][] = Array.from( { length: n + 1 }, () => Array(capacity + 1).fill(0) ); // Fill the table row by row for (let i = 1; i <= n; i++) { // Current item (0-indexed in arrays) const weightI = weights[i - 1]; const valueI = values[i - 1]; for (let c = 0; c <= capacity; c++) { // Case 1: Exclude current item dp[i][c] = dp[i - 1][c]; // Case 2: Include current item (if it fits) if (weightI <= c) { const includeValue = dp[i - 1][c - weightI] + valueI; dp[i][c] = Math.max(dp[i][c], includeValue); } } } return dp[n][capacity]; } // Example usage const weights = [2, 1, 3, 2]; const values = [12, 10, 20, 15]; const capacity = 5; console.log(`Maximum value: ${knapsackTabulation(weights, values, capacity)}`); // Output: Maximum value: 376f:T74d,def knapsack_with_items(weights: list[int], values: list[int], capacity: int) -> tuple[int, list[int]]: """ Solve 0/1 Knapsack and return both the max value and the selected items. Args: weights: List of item weights values: List of item values capacity: Maximum knapsack capacity Returns: Tuple of (max_value, list of selected item indices) """ n = len(weights) # Build the DP table dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): weight_i = weights[i - 1] value_i = values[i - 1] for c in range(capacity + 1): dp[i][c] = dp[i - 1][c] if weight_i <= c: dp[i][c] = max(dp[i][c], dp[i - 1][c - weight_i] + value_i) # Backtrack to find selected items selected_items = [] remaining_capacity = capacity for i in range(n, 0, -1): # If value changed from previous row, item i was included if dp[i][remaining_capacity] != dp[i - 1][remaining_capacity]: selected_items.append(i - 1) # Convert to 0-indexed remaining_capacity -= weights[i - 1] # Reverse to get items in original order selected_items.reverse() return dp[n][capacity], selected_items # Example usage if __name__ == "__main__": weights = [2, 1, 3, 2] values = [12, 10, 20, 15] capacity = 5 max_value, selected = knapsack_with_items(weights, values, capacity) print(f"Maximum value: {max_value}") print(f"Selected items (0-indexed): {selected}") print(" Selected item details:") for idx in selected: print(f" Item {idx}: weight={weights[idx]}, value={values[idx]}") total_weight = sum(weights[i] for i in selected) print(f" Total weight: {total_weight} / {capacity}")70:T58f,function knapsackWithItems( weights: number[], values: number[], capacity: number ): { maxValue: number; selectedItems: number[] } { const n = weights.length; // Build the DP table const dp: number[][] = Array.from( { length: n + 1 }, () => Array(capacity + 1).fill(0) ); for (let i = 1; i <= n; i++) { const weightI = weights[i - 1]; const valueI = values[i - 1]; for (let c = 0; c <= capacity; c++) { dp[i][c] = dp[i - 1][c]; if (weightI <= c) { dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - weightI] + valueI); } } } // Backtrack to find selected items const selectedItems: number[] = []; let remainingCapacity = capacity; for (let i = n; i > 0; i--) { if (dp[i][remainingCapacity] !== dp[i - 1][remainingCapacity]) { selectedItems.push(i - 1); // Convert to 0-indexed remainingCapacity -= weights[i - 1]; } } selectedItems.reverse(); return { maxValue: dp[n][capacity], selectedItems }; } // Example usage const weights = [2, 1, 3, 2]; const values = [12, 10, 20, 15]; const capacity = 5; const result = knapsackWithItems(weights, values, capacity); console.log(`Maximum value: ${result.maxValue}`); console.log(`Selected items: ${result.selectedItems}`);63:{"json":{"id":"seed_752b4fd33e156b94d97bcc193f0f3f1a","slug":"knapsack-problems","category":"Data Structures & Algorithms","topic":"Knapsack Problems","title":"Knapsack Problems — Resource-Constrained Optimization","description":"Master the knapsack family of dynamic programming problems. Learn to solve 0/1 knapsack, unbounded knapsack, and subset sum problems through systematic state design, optimal substructure analysis, and space-optimized implementations.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_0856ed7ab5272611ad2052cc8239959d","title":"0/1 Knapsack — The Classic Resource Allocation Problem","order":0,"content":[{"id":"opening-hook","title":"The Fundamental Resource Allocation Challenge","content":[{"data":{"content":"Imagine you're a treasure hunter standing before a chest of valuables, but your backpack has limited capacity. Each item has a weight and a value. You cannot exceed your capacity, and you cannot take fractions of items—it's all or nothing for each piece. How do you maximize the total value you carry away?\n\nThis seemingly simple scenario is the **0/1 Knapsack Problem**, and it stands as one of the most important problems in algorithm design and optimization theory. The \"0/1\" refers to the binary decision for each item: either you take it (1) or you leave it (0). No partial selections allowed.\n\nThe 0/1 Knapsack problem is not merely an academic curiosity—it models countless real-world optimization scenarios: investment portfolio selection with capital constraints, cargo loading with weight limits, task scheduling with resource budgets, and even cutting-stock problems in manufacturing. Mastering this problem provides a template for attacking an entire class of constrained optimization challenges."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the 0/1 Knapsack problem at a deep, structural level. You will learn to formalize the problem mathematically, understand why greedy approaches fail, develop the recurrence relation that enables dynamic programming, and implement both memoized and tabulated solutions. You'll also learn to reconstruct the optimal item selection, not just compute the optimal value.","variant":"info"},"type":"callout"}]},{"id":"problem-definition","title":"Formal Problem Definition","content":[{"data":{"content":"Let's establish a rigorous definition of the 0/1 Knapsack problem before diving into solutions.\n\n**Given:**\n- A set of `n` items, where item `i` has:\n - Weight: `w[i]` (positive integer)\n - Value: `v[i]` (positive integer or real number)\n- A knapsack with maximum capacity `W` (positive integer)\n\n**Find:**\nA subset S of items that maximizes the total value:\n\n$$\\text{maximize } \\sum_{i \\in S} v[i]$$\n\n**Subject to:**\n$$\\sum_{i \\in S} w[i] \\leq W$$\n\nThe key constraint is the binary decision for each item—each item is either fully included or fully excluded. This binary constraint is what distinguishes 0/1 Knapsack from its fractional counterpart, and it's precisely this constraint that makes the problem NP-hard in general."},"type":"text"},{"data":{"rows":[["Item 1","2","12","6.0"],["Item 2","1","10","10.0"],["Item 3","3","20","6.67"],["Item 4","2","15","7.5"]],"caption":"Example Knapsack Instance","headers":["Item","Weight","Value","Value/Weight Ratio"]},"type":"table"},{"data":{"content":"**Knapsack Capacity:** W = 5\n\nWith these items and capacity, what's the optimal selection? This is the question we'll answer through dynamic programming, but first let's understand why simpler approaches fail."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"why-greedy-fails","title":"Why Greedy Approaches Fail","content":[{"data":{"content":"Before committing to the complexity of dynamic programming, a natural question arises: can we solve this greedily? After all, if we could sort items by some criterion and greedily select them, we'd have an O(n log n) algorithm instead of the O(nW) dynamic programming solution.\n\nLet's examine the three most intuitive greedy strategies and understand why each fails:\n\n**Strategy 1: Greedy by Value**\nSelect items in decreasing order of value until the knapsack is full.\n\n**Strategy 2: Greedy by Weight**\nSelect items in increasing order of weight (lightest first) until full.\n\n**Strategy 3: Greedy by Value-to-Weight Ratio**\nSelect items in decreasing order of value-per-unit-weight.\n\nLet's test these on our example with W = 5:"},"type":"text"},{"data":{"rows":[["By Value (highest first)","Item 3 (20), Item 4 (15)","5","35","✓"],["By Weight (lightest first)","Item 2 (10), Item 1 (12), Item 4 (15)","5","37","✓"],["By Ratio","Item 2 (10), Item 4 (15), Item 3 ✗","3 (Item 3 doesn't fit)","25 + ...","✗"]],"caption":"Greedy Strategy Results (W = 5)","headers":["Strategy","Items Selected","Total Weight","Total Value","Optimal?"]},"type":"table"},{"data":{"content":"In this particular instance, some greedy strategies happen to find good solutions. But this is coincidental—greedy approaches can fail spectacularly on carefully constructed instances.\n\n**A Counterexample for All Greedy Strategies:**"},"type":"text"},{"data":{"rows":[["A","6","30","5.0"],["B","5","24","4.8"],["C","5","24","4.8"]],"caption":"Counterexample Instance (W = 10)","headers":["Item","Weight","Value","Ratio"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"Greedy Failure Analysis","content":"**Greedy by ratio:** Selects A (value 30, weight 6). Remaining capacity 4, nothing else fits. Total: 30.\n\n**Greedy by value:** Same result—A first, nothing else fits. Total: 30.\n\n**Optimal solution:** Select B + C. Weight: 5 + 5 = 10. Value: 24 + 24 = 48.\n\nEvery greedy strategy yields 30, but the optimal is 48—a 60% improvement! This demonstrates that no simple greedy criterion guarantees optimality for 0/1 Knapsack.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Fundamental Issue:**\n\nGreedy algorithms make irrevocable decisions at each step. For 0/1 Knapsack, selecting a high-value item early might consume capacity that could have been better used by a combination of smaller items. The problem lacks the **greedy choice property**—a locally optimal choice may foreclose globally optimal solutions.\n\nThis is precisely why we need dynamic programming: to consider all possible combinations systematically while avoiding the exponential blowup of brute-force enumeration."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"decision-at-each-step","title":"The Binary Decision Structure","content":[{"data":{"content":"The key insight for solving 0/1 Knapsack via dynamic programming is recognizing the **binary decision structure** inherent in the problem.\n\nFor each item, we face exactly two choices:\n1. **Include** the item in our knapsack\n2. **Exclude** the item from our knapsack\n\nThis binary fork creates a decision tree. For n items, there are 2^n possible subsets to consider—brute force would take exponential time. But here's the crucial observation: **many subproblems recur**.\n\nConsider deciding whether to include item `i`. Regardless of which items we selected from `{1, 2, ..., i-1}`, the decision for item `i` depends only on:\n1. Whether items `1` through `i` contribute to an optimal solution\n2. How much capacity remains\n\nThis structure enables us to define subproblems in terms of:\n- **Which items we've considered** (items 1 through i)\n- **What capacity remains** (0 through W)"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Principle of Optimality","content":"If we have an optimal solution that includes item i, then the remaining items must form an optimal solution for the remaining capacity. Similarly, if item i is excluded from an optimal solution considering items 1 to i, then the optimal solution for items 1 to (i-1) with the same capacity is also optimal for items 1 to i. This is optimal substructure.","variant":"tip"},"type":"callout"},{"data":{"content":"**Visualizing the Decision:**\n\nAt each item, we branch:\n\n```\n [Item i, Capacity c]\n |\n +---------------+---------------+\n | |\n [Exclude item i] [Include item i]\n | (if w[i] <= c)\n v v\n [Item i-1, Capacity c] [Item i-1, Capacity c - w[i]]\n + v[i]\n```\n\nThe recursive structure is now clear:\n- Excluding item `i` leaves us with the subproblem of items `1..i-1` with unchanged capacity\n- Including item `i` (if it fits) gives us `v[i]` plus the optimal solution for items `1..i-1` with reduced capacity\n\nWe take the maximum of these two choices."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"recurrence-relation","title":"The Recurrence Relation","content":[{"data":{"content":"Let's formalize the recursive structure into a precise recurrence relation. This is the heart of the dynamic programming solution.\n\n**Define:**\n`dp[i][c]` = Maximum value achievable using items `1, 2, ..., i` with knapsack capacity exactly `c`.\n\n**Recurrence:**"},"type":"text"},{"data":{"code":"// For all items i from 1 to n, and all capacities c from 0 to W:\n\ndp[i][c] = {\n // Base case: No items to choose from\n 0 if i == 0\n \n // Case 1: Item i is too heavy to include\n dp[i-1][c] if w[i] > c\n \n // Case 2: Item i fits; choose maximum of exclude vs include\n max(dp[i-1][c], otherwise\n dp[i-1][c - w[i]] + v[i])\n}\n\n// Final answer: dp[n][W]","fileName":"Recurrence Relation","showLineNumbers":true},"type":"code"},{"data":{"content":"**Breaking Down the Recurrence:**\n\n**Base Case (`i == 0`):**\nWith zero items available, the maximum value we can achieve is zero, regardless of capacity. This provides the foundation for building up solutions.\n\n**Item Too Heavy (`w[i] > c`):**\nIf item `i` weighs more than our current capacity `c`, we cannot include it. The optimal solution for items `1..i` with capacity `c` is simply the optimal solution for items `1..i-1` with the same capacity.\n\n**Item Fits (`w[i] <= c`):**\nWe have a genuine choice:\n- **Exclude item i:** `dp[i-1][c]` — the best we can do without item `i`\n- **Include item i:** `dp[i-1][c - w[i]] + v[i]` — the value of item `i` plus the best we can do with the remaining capacity and remaining items\n\nWe take the maximum because we want the optimal solution."},"type":"text"},{"data":{"icon":"Info","title":"Why This Recurrence is Correct","content":"The recurrence is correct because:\n\n1. **Exhaustive:** It considers both possibilities (include/exclude) for each item\n2. **Optimal Substructure:** Each subproblem is solved optimally before being used\n3. **No Overcounting:** The recurrence depends only on smaller subproblems\n\nEvery valid subset can be characterized by decisions on each item. The recurrence systematically explores all decisions.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"memoization-solution","title":"Top-Down Solution with Memoization","content":[{"data":{"content":"The most natural implementation directly translates the recurrence into recursive code with memoization. This approach starts from the original problem and recursively breaks it down, caching results to avoid recomputation.\n\n**Memoization Strategy:**\n- Use a 2D cache `memo[i][c]` to store computed values\n- Before computing a subproblem, check if it's already solved\n- After computing, store the result before returning"},"type":"text"},{"data":{"fileName":"knapsack_memoization.py","languages":[{"code":"$6a","label":"Python","value":"python"},{"code":"$6b","label":"TypeScript","value":"typescript"},{"code":"$6c","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Memoization Complexity Analysis","content":"**Time Complexity:** O(n × W)\n- We have at most (n+1) × (W+1) unique subproblems\n- Each subproblem is computed exactly once\n- Each computation takes O(1) time\n\n**Space Complexity:** O(n × W) for the memoization table, plus O(n) for the recursion stack.\n\nThe memoization approach is intuitive because it directly mirrors the recurrence, computing only the subproblems actually needed (on-demand).","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"tabulation-solution","title":"Bottom-Up Solution with Tabulation","content":[{"data":{"content":"The tabulation approach builds the solution iteratively from the ground up, filling a table in dependency order. This eliminates recursion overhead and provides better cache locality.\n\n**Table Structure:**\n`dp[i][c]` = Maximum value using first `i` items with capacity `c`\n\n**Fill Order:**\nWe fill row by row (increasing `i`), and within each row, left to right (increasing `c`). This ensures that when we compute `dp[i][c]`, we've already computed `dp[i-1][c]` and `dp[i-1][c-w[i]]`."},"type":"text"},{"data":{"fileName":"knapsack_tabulation.py","languages":[{"code":"$6d","label":"Python","value":"python"},{"code":"$6e","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Tracing Through the Example:**\n\nLet's trace through our example with items [(w=2, v=12), (w=1, v=10), (w=3, v=20), (w=2, v=15)] and capacity W=5:"},"type":"text"},{"data":{"rows":[["No items (i=0)","0","0","0","0","0","0"],["Item 1 (w=2,v=12)","0","0","12","12","12","12"],["Item 2 (w=1,v=10)","0","10","12","22","22","22"],["Item 3 (w=3,v=20)","0","10","12","22","30","32"],["Item 4 (w=2,v=15)","0","10","15","25","30","37"]],"caption":"DP Table Construction","headers":["","c=0","c=1","c=2","c=3","c=4","c=5"]},"type":"table"},{"data":{"content":"**Reading the Table:**\n\n- `dp[4][5] = 37` is our answer—the maximum value with all 4 items and capacity 5\n- At each cell, we chose the better of excluding or including the current item\n- For example, `dp[4][5] = max(dp[3][5], dp[3][3] + 15) = max(32, 22 + 15) = 37`\n\nThis tells us that including Item 4 is beneficial—we get 37 instead of the 32 we'd get without it."},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"reconstructing-solution","title":"Reconstructing the Optimal Item Selection","content":[{"data":{"content":"Finding the maximum value is often insufficient—we need to know **which items** to select. The DP table contains all the information needed to reconstruct the solution by tracing back through our decisions.\n\n**Backtracking Logic:**\n\nStarting from `dp[n][W]`, for each item `i` from `n` down to `1`:\n1. If `dp[i][c] != dp[i-1][c]`, item `i` was included (the value changed)\n2. If included, subtract `w[i]` from the remaining capacity and record item `i`\n3. If `dp[i][c] == dp[i-1][c]`, item `i` was excluded; move up without changing capacity"},"type":"text"},{"data":{"fileName":"knapsack_reconstruct.py","languages":[{"code":"$6f","label":"Python","value":"python"},{"code":"$70","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"CheckCircle","title":"Example Reconstruction","content":"For our example:\n- Start at dp[4][5] = 37\n- dp[4][5] ≠ dp[3][5] (37 ≠ 32) → Item 4 included, capacity becomes 5-2=3\n- dp[3][3] = dp[2][3] (22 = 22) → Item 3 excluded\n- dp[2][3] ≠ dp[1][3] (22 ≠ 12) → Item 2 included, capacity becomes 3-1=2\n- dp[1][2] ≠ dp[0][2] (12 ≠ 0) → Item 1 included, capacity becomes 2-2=0\n\n**Selected Items:** 1, 2, 4 (0-indexed: 0, 1, 3)\n**Total Value:** 12 + 10 + 15 = 37 ✓","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The 0/1 Knapsack Foundation","content":[{"data":{"content":"We've established a comprehensive understanding of the 0/1 Knapsack problem—the foundational problem of the knapsack family and a paradigmatic example of dynamic programming."},"type":"text"},{"data":{"type":"ordered","items":["**Binary Decision Structure:** Each item presents an include/exclude choice, creating a 2^n decision space that DP efficiently compresses.","**Greedy Approaches Fail:** No simple greedy criterion guarantees optimality because local decisions can foreclose better global solutions.","**Recurrence Relation:** dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) captures the essence of the problem.","**O(nW) Complexity:** Both time and space scale with items × capacity—this is pseudo-polynomial, not truly polynomial.","**Solution Reconstruction:** Backtracking through the DP table reveals which items comprise the optimal solution."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn the next page, we'll dive deeper into the **state representation**—understanding why we track \"capacity remaining\" as our state variable, and how this seemingly simple choice enables the entire dynamic programming approach. We'll also explore alternative state formulations and their implications."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the 0/1 Knapsack problem at a foundational level—from problem formulation through recurrence development to complete implementation with solution reconstruction. This forms the basis for all knapsack variants we'll explore in this module.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_d3f489cd5beb9feb4d74117f78db05df","title":"State Design — Capacity Remaining as the Key Dimension","order":1,"content":null,"isLocked":true},{"id":"seed_d4b90894ae8dd4f108f4d750df2b29d3","title":"Unbounded Knapsack — Unlimited Item Selections","order":2,"content":null,"isLocked":true},{"id":"seed_73963174cbedfe180de8feab7ea2eafb","title":"Subset Sum — A Specialized Knapsack Problem","order":3,"content":null,"isLocked":true}]}}