What is the brute force approach and complexity for 0/1 Knapsack?

For each item, try skipping it and taking it; keep the best total with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for 0/1 Knapsack?

Keep one row dp[c]; for each item, update it with c going from W down to the item's weight with optimal time complexity O(N · W) and space complexity O(W).

How do you identify the pattern for 0/1 Knapsack?

Look for key signals in the prompt: "each item at most once" indicates Each item is either in or out, and it can be used only once → 0/1 knapsack. The capacity loop runs high → low.; "total weight at most W" indicates The room left in the bag is the state. dp[c] stores the best value for each room c.; "largest total value" indicates Every cell is a max of two choices: skip the item or take it..

0/1 Knapsack

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelDP — Knapsack → 0/1 knapsack (one row)

Complexity:O(2^N)→O(N · W)

Key Insight

Each row only reads the row above it, so keep one row and update it in place. For each item, let c run from W down to wt, and set dp[c] = max(dp[c], val + dp[c − wt]). Because c goes down, dp[c − wt] is still the old row when it is read, so each item is counted at most once.

Core Validity Invariant

dp[c] is the best value for room c using each item at most once, and this holds because the loop goes c high → low: the cell it reads, dp[c − wt], is still the value from before this item.

Problem

You have a bag that can hold a total weight of at most W. There are n items. Item i has a value val[i] and a weight wt[i].

You may take each item at most once. Choose a set of items whose total weight is at most W, so that their total value is as large as possible.

Return that largest total value. The function is int knapsack(int W, vector<int>& val, vector<int>& wt).

Input

W, the weight limit. val and wt, two lists of the same length: the value and the weight of each item.

Output

A single number: the largest total value of a set of items whose total weight is at most W.

Example 1

Input: W = 4, val = [1, 2, 3], wt = [4, 5, 1]

Output: 3

Item 1 (weight 4) is worth 1 on its own. Item 2 weighs 5, which is over the limit. Item 3 (weight 1) is worth 3. Items 1 and 3 together weigh 5, which is too much, so the best is item 3 alone.

Example 2

Input: W = 50, val = [60, 100, 120], wt = [10, 20, 30]

Output: 220

Items 2 and 3 weigh 20 + 30 = 50, exactly the limit, and are worth 100 + 120 = 220. Adding item 1 would push the weight past 50.

Example 3

Input: W = 3, val = [1, 2, 3], wt = [4, 5, 6]

Output: 0

Every item weighs more than 3, so nothing fits.

Constraints

• 1 ≤ W ≤ 10^3
• 1 ≤ n ≤ 10^3, and val and wt have the same length
• 1 ≤ val[i] ≤ 10^3
• 1 ≤ wt[i] ≤ 10^3

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Can I take the same item twice here? What in the statement tells me?
2.
For the first item, I either take it or I do not. What is left for the other items in each case?
3.
The room left in the bag shrinks as I take items. What should I remember about each possible room size?
4.
If I always take the item with the best value for its weight first, will I always get the best total? Try a small example.
5.
How many (number of items considered, room left) pairs are there, and could I fill them in one by one?

Brute force approach

Idea

Go through the items one by one. For each item there are two choices: skip it, or take it (only when it fits) and add its value. The answer is the bigger of the two results. Every combination of items gets tried, with no memory between calls.

Thinking process

1
Take the example W = 4, with item 1 (w 4, v 1), item 2 (w 5, v 2) and item 3 (w 1, v 3).
2
At item 1 with room 4, skipping leaves the other items to choose from. Taking is allowed (4 ≤ 4), and it leaves room 0.
3
At item 2, the weight 5 is more than any room we can have here (at most 4), so the only choice is skip.
4
At item 3, the weight is 1, so taking it is allowed whenever the room is at least 1. Taking it gives value 3.
5
Check the answer: item 3 alone gives 3. Items 1 and 3 together weigh 5, which is over 4, so they are not allowed. The best is 3.

Visual

Each node is a call i|room: items from index i on, with room left. Orange = the same (i, room) was already solved by an earlier call; the brute force solves it again. Blue = the path from the top to the current call. Red ✗ = too heavy, no take branch.

Brute force: take or skip every itemW = 3, val = [3, 4, 5], wt = [1, 1, 2]step 1/23

calls

▲i

val

▲i

Work

calls: 1
repeated states: 0
room left: 3

Call 0|3: items from 0 on, room 3

Item 1 (w 1, v 3) with room 3.

Code & Implementation

brute.cpp

class Solution {
    // Best value we can get from items i, i+1, ... when `left` capacity remains.
    int best(vector<int>& val, vector<int>& wt, int i, int left) {
        if (i == (int)wt.size()) return 0;                // no items left
        int skip = best(val, wt, i + 1, left);            // leave item i out
        if (wt[i] > left) return skip;                    // too heavy: skipping is the only choice
        int take = val[i] + best(val, wt, i + 1, left - wt[i]);  // take item i, use up its weight
        return max(skip, take);
    }

public:
    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        // Try every take / skip choice for every item. Nothing is remembered between calls.
        return best(val, wt, 0, W);
    }
};

Complexity

Time O(2^N)Space O(N)

Every item has two branches, so there are up to 2^N calls. The recursion goes N levels deep, which is the O(N) space. With N up to 10^3, this will never finish.

Better approach

Why brute force is slow

The brute force has no memory. It solves the same (items left, room) pair again every time a path reaches it.

What repeated work are we doing?

In the visual example (weights 1, 1, 2 and room 3), the call "items from index 2 on, room 2" is solved twice.

What information can we reuse?

There are only (N + 1) × (W + 1) pairs. The table stores each one once, and each cell is a single O(1) step.

New approach

Idea

Let dp[i][c] be the best value using only the first i items with room c. Each cell reads two cells in the row above: skip, which is dp[i − 1][c], and take, which is val + dp[i − 1][c − wt]. Fill the table row by row. The answer is dp[n][W].

Thinking process

1
The brute force asks the same (items left, room) question many times. A table stores each question once.
2
Row 0 means no items are allowed, so every cell in it is 0.
3
Row 1 is item 1 (w 4, v 1). Only room 4 can take it: dp[1][4] = max(dp[0][4], 1 + dp[0][0]) = max(0, 1) = 1.
4
Row 3 is item 3 (w 1, v 3). At room 4, take gives 3 + dp[2][3] = 3 + 0 = 3, and skip gives dp[2][4] = 1. The bigger is 3.
5
So dp[3][4] = 3, which matches the answer.

Visual

Rows are items (row 0 = no items), columns are capacity 0 … W. Each cell takes the better of the cell above (skip) and the cell above, w to the left, plus the value (take). Blue = cells read; purple = a take that wins.

2-D table: items × capacityW = 4, val = [1, 2, 3], wt = [4, 5, 1]step 1/17

dp[i][c]: rows = items considered, columns = capacity

val

State

row 0: no items: all 0

Row 0 = no items. Every cell is 0

Row 0 means no items are allowed yet, so every capacity is worth 0. Each later row adds one item.

Code & Implementation

better.cpp

class Solution {
public:
    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        int n = wt.size();

        // dp[i][c] = best value using only the first i items, with capacity c.
        // Row 0 means "no items yet", so every cell in it is 0.
        vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= W; c++) {
                dp[i][c] = dp[i - 1][c];                  // skip item i (index i - 1)
                if (wt[i - 1] <= c)                       // take it only if it fits
                    dp[i][c] = max(dp[i][c], val[i - 1] + dp[i - 1][c - wt[i - 1]]);
            }
        }
        return dp[n][W];
    }
};

Complexity

Time O(N · W)Space O(N · W)

N is the number of items and W is the capacity. The table has N + 1 rows of W + 1 cells, and each cell is O(1). Every cell reads the row above, so the whole table is kept.

Optimized approach

Idea

Start from brute force

The brute force calls the same (items left, room) pair again and again. Each call only needs those two numbers, so the answer for each pair can be stored once.

Find the repeated work

The same (item, room) pair is solved on many different paths. The table keeps one answer per pair, and the row trick keeps only the row we still need.

Define the state — what variables do I need?

dp[c]: The best value that fits in room `c`, using only the items seen so far.
item: The item being added now. It is used in one pass only.
c: The room being updated in this pass. It goes from W down to the item's weight.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Before the first item

dp[c] = 0 for every c

With no items, nothing has any value, so every room is worth 0.

For each item, c from W down to wt

dp[c] = max(dp[c], val + dp[c − wt])

The bigger of skip (the old dp[c]) and take (the item plus the best for the room left before it) is the new best for room c.

The item weighs more than W

The loop does not run

c never reaches wt, so the item can never be taken and the row stays the same.

What does the current window add to the answer?

After all the items, dp[W] is the best value that fits in the whole bag.

Code & Implementation

optimal.cpp

class Solution {
public:
    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        int n = wt.size();

        // dp[c] = best value that fits in capacity c, using the items seen so far.
        vector<int> dp(W + 1, 0);
        for (int i = 0; i < n; i++) {
            // High → low: dp[c - wt[i]] still holds the row from before item i,
            // so item i can add its value only once. An item heavier than W never enters the loop.
            for (int c = W; c >= wt[i]; c--)
                dp[c] = max(dp[c], val[i] + dp[c - wt[i]]);
        }
        return dp[W];
    }
};

Complexity

Time O(N · W)Space O(W)

Each of the N items runs a loop over at most W capacities. Only one row of W + 1 values is stored.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each item, try skipping it and taking it; keep the best total	O(2^N)	O(N)
Better	Fill dp[i][c] once for every (item count, room) pair; each cell is O(1)	O(N · W)	O(N · W)
Optimal	Keep one row dp[c]; for each item, update it with c going from W down to the item's weight	O(N · W)	O(W)

Why does this belong to this pattern?

Clues in the problem statement

“each item at most once”Each item is either in or out, and it can be used only once → 0/1 knapsack. The capacity loop runs high → low.
“total weight at most W”The room left in the bag is the state. dp[c] stores the best value for each room c.
“largest total value”Every cell is a max of two choices: skip the item or take it.

Choose items with total weight ≤ W+each item at most once+maximise total value→DP — Knapsack → 0/1 knapsack (one row)

This is the anchor of the Knapsack pattern. The only thing that makes it 0/1 is the loop direction: going high → low means an item cannot feed itself. Subset Sum is this same row with true/false instead of values, and Ones and Zeroes adds a second capacity under the same rule.

Don't make this mistake

Pattern confusion: looping c low → high

✗ for (int c = wt[i]; c <= W; c++) dp[c] = max(dp[c], val[i] + dp[c - wt[i]]);

✓ for (int c = W; c >= wt[i]; c--) dp[c] = max(dp[c], val[i] + dp[c - wt[i]]);

Going up reads dp[c − wt] after it was already updated for this same item, so the item adds its value again. On W = 4, val = [1, 2, 3], wt = [4, 5, 1], item 3 (w 1, v 3) becomes dp = 0, 3, 6, 9, 12. The answer 12 uses the weight-1 item four times. The correct answer is 3.

Greedy: take the best value-per-weight first

✗ sort by val / wt, then take each item that still fits

✓ fill the dp row (it considers every subset)

Take W = 50 with items (w 10, v 60), (w 20, v 100) and (w 30, v 120). The ratios are 6, 5 and 4. Greedy takes the first two (weight 30, value 160), and then item 3 does not fit into the 20 left. Items 2 and 3 are worth 220. Greedy only works when you can take part of an item.

Forgetting the skip option

✗ dp[c] = val[i] + dp[c - wt[i]];

✓ dp[c] = max(dp[c], val[i] + dp[c - wt[i]]);

Overwriting drops the choice to skip. On W = 4, with items (w 1, v 3) and then (w 4, v 1), the answer is 3. The overwrite sets dp[4] = 1 + dp[0] = 1 when the second item is processed, which throws away the 3.

Missing the size check

✗ for (int c = W; c >= 0; c--) dp[c] = max(dp[c], val[i] + dp[c - wt[i]]);

✓ for (int c = W; c >= wt[i]; c--) dp[c] = max(dp[c], val[i] + dp[c - wt[i]]);

When c < wt[i], the index c − wt[i] is negative, so the read goes outside the array. With W = 4 and an item of weight 5, the loop reads dp[−1].

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture