DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master the classic 0/1 Knapsack problem with 2D DP table construction, include/exclude decisions, solution traceback, and space optimization.
The Problem
You have a knapsack with weight capacity W and n items. Each item has a weight wt[i] and value val[i]. You must choose a subset of items to maximize total value without exceeding the weight capacity. Each item is either taken completely or left (0/1 — no fractions).
Example: Capacity = 7, Items: {(weight=1, value=1), (weight=3, value=4), (weight=4, value=5), (weight=5, value=7)}
Why Greedy Fails
You might think: "Just take items with the best value-per-weight ratio." But that does not always work for 0/1 knapsack:
- Item A: weight=3, value=4 (ratio=1.33)
- Item B: weight=4, value=5 (ratio=1.25)
- Item C: weight=5, value=7 (ratio=1.40)
With capacity=7: Greedy picks C first (best ratio), then can only fit A. Total value=11. But the optimal is A+B: weight=7, value=9... wait, that is less. Let us try: B+A gives 4+5=9. Actually C+A gives 7+4=11, and A+B gives 4+5=9. So greedy was right here. But consider: capacity=7, items (4,5), (3,4), (3,4). Greedy might pick (4,5) and one (3,4)=9. But two (3,4)=8 is worse. The point is greedy can fail in general.
The key issue: 0/1 constraint means you cannot take fractions, so ratio-based greedy gives no guarantees.
The DP Approach
State: dp[i][w] = maximum value achievable using items 0..i-1 with capacity w
Transition: For each item i and capacity w:
- Skip item i:
dp[i][w] = dp[i-1][w] - Take item i (if
wt[i] <= w):dp[i][w] = dp[i-1][w - wt[i]] + val[i] - Choose the better:
dp[i][w] = max(skip, take)
Base case: dp[0][w] = 0 for all w (no items = no value)
Step-by-Step Example
| Items | weight=[1, 3, 4, 5], value=[1, 4, 5, 7], Capacity=7 |
| i=1 0 1 1 1 1 1 1 1 (item | wt=1, val=1) |
| i=2 0 1 1 4 5 5 5 5 (item | wt=3, val=4) |
| i=3 0 1 1 4 5 6 6 9 (item | wt=4, val=5) |
| i=4 0 1 1 4 5 7 8 9 (item | wt=5, val=7) |
| Answer | dp[4][7] = 9 |
| How? At i=3, w=7 | max(dp[2][7], dp[2][7-4]+5) = max(5, dp[2][3]+5) = max(5, 4+5) = 9 |
| This means | take item 3 (val=5) + best from items 0-2 with remaining capacity 3 = item 2 (val=4) |
| Items chosen | item 2 (wt=3,val=4) + item 3 (wt=4,val=5) = weight 7, value 9 ✓ |
Python Implementation
Example
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = max value using first i items with capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Option 1: skip item i
dp[i][w] = dp[i-1][w]
# Option 2: take item i (if it fits)
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# Example
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 9
Traceback: Finding Which Items Were Chosen
Example
def knapsack_with_items(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):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
# Traceback: find which items were selected
selected = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i-1][w]: # Item i was taken
selected.append(i - 1)
w -= weights[i-1]
return dp[n][capacity], selected
max_val, items = knapsack_with_items(weights, values, capacity)
print(f"Max value: {max_val}, Items: {items}") # Max value: 9, Items: [2, 1]
Space Optimized: O(W) Space
Since dp[i][w] only depends on dp[i-1][...], we can use a single 1D array. The trick: iterate capacity in REVERSE to avoid overwriting values we still need.
Example
def knapsack_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# Iterate in reverse to ensure each item is used at most once
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
Why reverse? If we iterate forward, dp[w - weights[i]] might already be updated in this iteration (meaning we used item i twice). Reverse ensures we read "previous row" values.
C++ Implementation
Example
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(vector<int>& wt, vector<int>& val, int W) {
int n = wt.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++)
for (int w = W; w >= wt[i]; w--)
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
Time and Space Complexity
- 2D version: Time O(n × W), Space O(n × W)
- 1D optimized: Time O(n × W), Space O(W)
- Note: This is pseudo-polynomial — polynomial in W (the value), not in the input size. If W is exponentially large, this is slow.
Variations
Unbounded Knapsack (items can be reused)
Use forward iteration instead of reverse:
Example
for w in range(weights[i], capacity + 1): # Forward = allow reuse
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
Subset Sum (can we make exact weight W?)
Example
dp = [False] * (W + 1)
dp[0] = True
for w in weights:
for j in range(W, w - 1, -1):
dp[j] = dp[j] or dp[j - w]
Count of subsets with given sum
Example
dp = [0] * (W + 1)
dp[0] = 1
for w in weights:
for j in range(W, w - 1, -1):
dp[j] += dp[j - w]
Real-World Applications
- Budget allocation: Choose projects maximizing profit within budget
- Cargo loading: Load containers maximizing value within weight limit
- Resource scheduling: Assign resources maximizing utilization
- Portfolio optimization: Select investments maximizing return within risk budget
- Cutting stock: Cut material pieces maximizing usage from limited stock
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for 0/1 Knapsack Problem.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, dynamic, programming, knapsack
Related Data Structures & Algorithms Topics
Continue learning this concept
Dynamic ProgrammingDynamic Programming Interview ProblemsMaster essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.Dynamic ProgrammingDynamic Programming FundamentalsUnderstand the core principles of dynamic programming: overlapping subproblems, optimal substructure, and how DP differs from divide-and-conquer and greedy approaches.Dynamic ProgrammingFibonacci with Dynamic ProgrammingSee how DP transforms Fibonacci from exponential O(2^n) naive recursion to O(n) memoization, O(n) tabulation, and O(1) space-optimized solution.Dynamic ProgrammingLongest Common Subsequence (LCS)Master the LCS problem with 2D DP table construction, backtracking for the actual subsequence, and its application in diff utilities.Dynamic ProgrammingLongest Increasing Subsequence (LIS)Solve LIS with O(n\u00b2) DP approach and the optimal O(n log n) patience sorting algorithm, with complete analysis and code.Dynamic ProgrammingMatrix Chain MultiplicationMaster the matrix chain multiplication problem with optimal parenthesization, gap-based DP table filling, and complete implementation.