Log inSign up
mediumGeeksforGeeksNot Started

0/1 Knapsack

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

You are given N items, each with a specific weight wt[i] and value val[i]. You also have a knapsack with a maximum weight capacity W.

Your task is to determine the maximum total value of items you can pack into the knapsack such that the sum of their weights does not exceed W.

Each item can either be taken once (1) or not taken at all (0), hence the name 0/1 Knapsack. Fractional items are strictly not permitted.

### Example 1 - Input: val = [60, 100, 120], wt = [10, 20, 30], W = 50 - Output: 220 - Explanation: Pick items with weights 20 and 30 for a combined weight of 50 and total value 100 + 120 = 220.

### Example 2 - Input: val = [10, 40, 30, 50], wt = [5, 4, 6, 3], W = 5 - Output: 50 - Explanation: Take the 4th item with weight 3 and value 50. Remaining capacity 2 cannot accommodate any remaining item.

Constraints:

  • 1 <= N <= 1000
  • 1 <= W <= 1000
  • 1 <= wt[i] <= 1000
  • 1 <= val[i] <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the fundamental recurrence relation of choice under capacity constraints.
  • Understand why reverse 1D array iteration prevents using the same item multiple times in 0/1 knapsack.
  • Apply state-space reduction techniques from O(N * W) 2D memory to O(W) 1D memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Given weights/costs and values with a strict upper budget/capacity.
  • Each item can be picked at most once.
  • Finding max/min value or exact subset reachability.

Algorithmic Decision Tree:

  • If each item can only be picked once -> 0/1 Knapsack (reverse 1D array loop).
  • If items can be picked infinitely -> Unbounded Knapsack (forward 1D array loop).

Connected Patterns:

Subset SumPartition Equal Subset SumTarget SumCoin Change

1. Recursive Exhaustive Search (Include/Exclude)

Intuition

For each item from 0 to N-1, branch into two decisions: take the item if wt[i] <= W, or skip it. Return the maximum value obtained from both branches.

Algorithm

  1. Define helper function solve(i, remainingW).
  2. Base Case: If i == N or remainingW == 0, return 0.
  3. If wt[i] > remainingW, we cannot include item i; return solve(i + 1, remainingW).
  4. Otherwise, compute take = val[i] + solve(i + 1, remainingW - wt[i]) and notTake = solve(i + 1, remainingW).
  5. Return max(take, notTake).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int knapsackRecursive(int i, int W, const vector<int>& wt, const vector<int>& val) {
8 if (i == (int)wt.size() || W == 0) return 0;
9 if (wt[i] > W) {
10 return knapsackRecursive(i + 1, W, wt, val);
11 }
12 int take = val[i] + knapsackRecursive(i + 1, W - wt[i], wt, val);
13 int notTake = knapsackRecursive(i + 1, W, wt, val);
14 return max(take, notTake);
15}
16
17int main() {
18 vector<int> val = {60, 100, 120};
19 vector<int> wt = {10, 20, 30};
20 int W = 50;
21 cout << "Max Knapsack Value: " << knapsackRecursive(0, W, wt, val) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N) recursion stack space

2. 2D Dynamic Programming (Tabulation)

Intuition

Construct a 2D table dp[N + 1][W + 1] where dp[i][w] represents the maximum value achievable using the first i items within weight limit w.

Algorithm

  1. Create dp of size (N + 1) x (W + 1) filled with 0.
  2. For i from 1 to N:
  3. For w from 0 to W:
  4. If wt[i - 1] <= w, dp[i][w] = max(dp[i - 1][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]).
  5. Else, dp[i][w] = dp[i - 1][w].
  6. Return dp[N][W].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int knapsack2D(int W, const vector<int>& wt, const vector<int>& val) {
8 int n = wt.size();
9 vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
10
11 for (int i = 1; i <= n; i++) {
12 for (int w = 0; w <= W; w++) {
13 if (wt[i - 1] <= w) {
14 dp[i][w] = max(dp[i - 1][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]);
15 } else {
16 dp[i][w] = dp[i - 1][w];
17 }
18 }
19 }
20 return dp[n][W];
21}
22
23int main() {
24 vector<int> val = {60, 100, 120};
25 vector<int> wt = {10, 20, 30};
26 int W = 50;
27 cout << "2D DP Max Value: " << knapsack2D(W, wt, val) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N * W)
  • Space complexity: O(N * W) 2D array

3. 1D Array Space-Optimized Dynamic Programming

Intuition

Use a single 1D array of size W + 1. Traverse capacity w backwards from W down to wt[i] to ensure each item is considered at most once without overwriting needed states.

Algorithm

  1. Initialize array dp of size W + 1 with 0.
  2. For each item i from 0 to N - 1:
  3. For capacity w from W down to wt[i]:
  4. dp[w] = max(dp[w], val[i] + dp[w - wt[i]]).
  5. Return dp[W].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int knapsackOptimal(int W, const vector<int>& wt, const vector<int>& val) {
8 int n = wt.size();
9 vector<int> dp(W + 1, 0);
10
11 for (int i = 0; i < n; i++) {
12 for (int w = W; w >= wt[i]; w--) {
13 dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
14 }
15 }
16 return dp[W];
17}
18
19int main() {
20 vector<int> val = {60, 100, 120};
21 vector<int> wt = {10, 20, 30};
22 int W = 50;
23 cout << "Optimal 1D DP Max Value: " << knapsackOptimal(W, wt, val) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N * W)
  • Space complexity: O(W) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive ExhaustiveO(2^N)O(N)Branching choice for every item (include or exclude).Recomputes overlapping states
2.2D DP TableO(N * W)O(N * W)Memoize state (i, w) in a 2D matrix.Full matrix storage
3.1D Array OptimizedOptimalO(N * W)O(W)Iterate capacity backwards in a single 1D array.Pseudo-polynomial time O(N * W)

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating inner loop forwards in 1D array: turns 0/1 knapsack into unbounded knapsack.

Pitfall 2:

Off-by-one errors with 1-based indexing in 2D array: confusing dp[i-1][w] with item index i-1.

Pitfall 3:

Assuming greedy value-to-weight ratio always works: Greedy fails for 0/1 knapsack (it only works for Fractional Knapsack).

Crucial Edge Cases to Validate:

  • W = 0: Output must be 0 immediately without processing.
  • All item weights greater than W: Output must be 0.
  • Single item: If wt[0] <= W, return val[0], else return 0.
  • Large W: Memory overflow if allocating arrays when W > 107; branch-and-bound or meet-in-the-middle would be required.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always clarify if items can be reused (0/1 vs Unbounded).
  2. Mention that 0/1 knapsack is NP-Complete and that DP is pseudo-polynomial.
  3. Immediately demonstrate the progression from 2D DP to 1D space-optimized DP to impress the interviewer.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the inner capacity loop iterate downwards (from W down to wt[i]) when using a 1D DP array for 0/1 knapsack?

2.What is the time complexity class of the 0/1 knapsack problem when solved via Dynamic Programming?

Back to DSA Sheet