What is the brute force approach and complexity for Knapsack with Duplicate Items?

Recurse over the items: skip each one, or take one copy and stay on it. No memory. with time complexity O(2^(N + W)) and space complexity O(N + W).

What is the optimal approach and complexity for Knapsack with Duplicate Items?

One array dp[c]; for each item, go over c from its weight up to capacity with optimal time complexity O(N · W) and space complexity O(W).

How do you identify the pattern for Knapsack with Duplicate Items?

Look for key signals in the prompt: "you may take the same item as many times as you like" indicates Items can repeat, so this is the unbounded knapsack. The capacity loop goes low → high.; "total weight is at most the capacity" indicates The bag has room c, so the table is indexed by capacity.; "biggest total value" indicates Keep the best of the choices: skip the item, or add one more copy of it..

Knapsack with Duplicate Items

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelDP — Knapsack, Unbounded (one row, capacity low → high)

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

Key Insight

Keep one row: dp[c] is the best value that fits in capacity c using the items seen so far. For each item, go over c from the item's weight up to the capacity, low → high. When we reach c, the cell dp[c − w] was already updated for this item, so it may already hold a copy of it. That is what lets the item repeat.

Core Validity Invariant

After each pass, dp[c] is the best value that fits in capacity c using the items so far, and this holds because dp[c − w] may already include a copy of the current item, which is exactly the repeat we want.

Problem

You have a bag that can hold a total weight of capacity. You also have n kinds of items. Item i has a weight wt[i] and a value val[i].

You may take the same kind of item as many times as you like. Find the biggest total value you can pack without going over the capacity.

The function returns that biggest total value. It does not need to say which items were taken.

Input

Two lists val and wt of the same length n (the value and weight of each kind of item), and the integer capacity.

Output

One number: the largest total value of a set of items (repeats allowed) whose total weight is at most capacity.

Example 1

Input: val = [5, 7], wt = [2, 3], capacity = 7

Output: 17

Take item A twice (weight 4, value 10) and item B once (weight 3, value 7). The weight is 7 and the value is 17. No other mix that fits is worth more.

Example 2

Input: val = [10, 40, 50, 70], wt = [1, 3, 4, 5], capacity = 8

Output: 110

Take the item with weight 3 (value 40) and the item with weight 5 (value 70). The weight is 8 and the value is 110.

Example 3

Input: val = [1, 1], wt = [2, 1], capacity = 3

Output: 3

Take the weight-1 item three times: weight 3, value 3.

Constraints

• 1 ≤ capacity, val.size() ≤ 1000
• 1 ≤ val[i], wt[i] ≤ 100
• wt.size() = val.size()

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 kind of item more than once here? How does that change what a single decision looks like?
2.
If I already know the best value for a smaller bag, how could it help me with a bigger bag?
3.
For one capacity, which choices do I have for the item I am looking at right now?
4.
If I fill the bag from the smallest capacity to the biggest, which cells already hold a new value when I read them?
5.
How many (item, capacity) pairs are there, and how many calls would a recursion make for them?

Brute force approach

Idea

Go through the items in order. At each item, either skip it, or take one copy and stay on the same item, because it can be taken again. Stop when the items run out or the bag has no room. Keep the better of the two choices.

Thinking process

1
Use val = [5, 7], wt = [2, 3], capacity = 7. Start at item A with room 7.
2
Take A: value 5, room 5, and we are still on A. Take A again: value 10, room 3. Take A again: value 15, room 1. Nothing fits in room 1, so this branch is worth 15.
3
Back at room 3 on item A, skip A and move to B. Take B: value 10 + 7 = 17, room 0. That beats 15, so 17 is the best so far.
4
The same pair shows up on different paths. Item B with room 1 is reached from B with room 4 and from A with room 1, so it is worked out twice.

Visual

Each circle is one call: i|c = item index | room left. Blue path = the calls now open. Orange = a repeat: that (item, room) pair was already solved earlier. Brute force does not remember answers, so it works them out again.

Brute force: take-and-stay recursionitems: A (weight 2, value 5), B (weight 3, value 7); capacity = 7step 1/31

calls

items

A w2 v5

B w3 v7

▲i

State

item i: A
room c: 7
calls: 1
repeated calls: 0

Item A, room 7

First the skip branch (never take A). Then, if A fits, the take branch.

Code & Implementation

brute.cpp

class Solution {
    // best(i, c): the most value we can add using items i, i+1, ... with c weight of room left.
    // Take-and-stay: after taking item i we decide again with the same i, so it can be taken again.
    int best(vector<int>& val, vector<int>& wt, int i, int c) {
        if (i == (int)wt.size() || c == 0) return 0;      // no items left, or no room left
        int skip = best(val, wt, i + 1, c);               // never take item i
        if (wt[i] > c) return skip;                       // item i does not fit
        int take = val[i] + best(val, wt, i, c - wt[i]);  // take item i, then decide again (same i)
        return max(skip, take);
    }

public:
    int knapSack(vector<int>& val, vector<int>& wt, int capacity) {
        return best(val, wt, 0, capacity);
    }
};

Complexity

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

N is the number of items and W is the capacity. Each call either moves on to the next item or lowers the room by at least 1, so a path has at most N + W steps, and each step has two branches. The same (item, room) pair is worked out again on every path that reaches it. The space is the recursion depth, at most N + W.

Better approach

Why brute force is slow

The brute force asks the same (item, room) question from several paths. Item B with room 1 is worked out twice in the brute tree.

What repeated work are we doing?

Each pair (item i, room c) is recomputed every time a path reaches it, so the number of calls grows exponentially.

What information can we reuse?

Fill every (item, room) pair once in a table. A cell only reads the row above or an earlier column of its own row, and both are already filled.

New approach

Idea

Build a table with one row per item (row 0 means no items) and one column per capacity. Cell dp[i][c] is the best value using only the first i items with room c. Each cell takes the better of the cell above (skip the item) and the cell w columns to the left in the same row (take one more copy).

Thinking process

1
Each cell only looks at a smaller room in the same row, or at the row above. A pair that the brute force worked out twice can be stored once.
2
Row A (weight 2, value 5). Column 2: skip gives dp[0][2] = 0; take gives dp[1][0] + 5 = 5. So dp[1][2] = 5.
3
Column 4: skip gives 0; take gives dp[1][2] + 5 = 10. The cell dp[1][2] is in the same row, already filled, and it holds one A, so dp[1][4] = 10 (two copies of A).
4
Row B (weight 3, value 7). Column 7: skip gives dp[1][7] = 15 (three copies of A); take gives dp[2][4] + 7 = 10 + 7 = 17. So dp[2][7] = 17.

Visual

Rows = items considered (row 0 = no items), columns = capacity 0 … 7. Blue = the cells read: the cell above (skip) and the cell to the left by the item's weight in the same row (take). Green = filled. Purple = the answer.

Unbounded knapsack: the 2D tableitems: A (weight 2, value 5), B (weight 3, value 7); capacity = 7step 1/18

dp[i][c]

State

rows: i = 0 … 2
columns: c = 0 … 7

Row 0 = no items: every capacity is worth 0

Each row only reads itself and the row above. The first row is filled with 0s before any item is considered.

Code & Implementation

better.cpp

class Solution {
public:
    int knapSack(vector<int>& val, vector<int>& wt, int capacity) {
        int n = wt.size();
        // dp[i][c] = most value we can get from 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>(capacity + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= capacity; c++) {
                dp[i][c] = dp[i - 1][c];                          // skip item i: the row above
                if (wt[i - 1] <= c)                               // take item i: read the SAME row,
                    dp[i][c] = max(dp[i][c],                      // because dp[i][c - w] may already
                                   dp[i][c - wt[i - 1]] + val[i - 1]);  // include another copy of item i
            }
        }
        return dp[n][capacity];
    }
};

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 takes constant time. Keeping every row is what makes the space O(N · W).

Optimized approach

Idea

Start from brute force

The brute force tries take and skip for every item, and it works out the same (item, room) pairs again on different paths.

Find the repeated work

Two paths can reach the same item with the same room, and each time the whole sub-search runs again. A table stores the answer for each pair once.

Define the state — what variables do I need?

dp[c]: The most value that fits in capacity `c`, using the items processed so far. dp[0] is 0, since nothing fits in no room.
i: The item being added. All of its copies are added in one pass over the capacities.
c: The capacity being filled in this pass, from the item's weight up to the capacity.

Define validity

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

For each item (weight w, value v), c from w up to capacity

dp[c] = max(dp[c], dp[c − w] + v)

dp[c] still holds the answer without this item. dp[c − w] is at a smaller capacity, so this pass already updated it. Taking one more copy of the item is therefore allowed.

Before the loops

Set dp[0 … capacity] = 0

With no items chosen, no capacity has any value yet.

What does the current window add to the answer?

After the last item, dp[capacity] is the best value for the whole bag, and every smaller capacity is also correct in the same array.

Code & Implementation

optimal.cpp

class Solution {
public:
    int knapSack(vector<int>& val, vector<int>& wt, int capacity) {
        vector<int> dp(capacity + 1, 0);                  // dp[c] = most value that fits in capacity c
        for (int i = 0; i < (int)wt.size(); i++) {
            // Low → high: when we reach c, dp[c - wt[i]] already includes item i,
            // so item i can be added again. High → low would make it a 0/1 knapsack.
            for (int c = wt[i]; c <= capacity; c++)
                dp[c] = max(dp[c], dp[c - wt[i]] + val[i]);
        }
        return dp[capacity];
    }
};

Complexity

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

N is the number of items and W is the capacity. The two loops visit each (item, capacity) pair once. The space is one array of W + 1 values, because each row only needs the one before it.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse over the items: skip each one, or take one copy and stay on it. No memory.	O(2^(N + W))	O(N + W)
Better	dp[i][c] = best value using the first i items with room c; each cell is worked out once	O(N · W)	O(N · W)
Optimal	One array dp[c]; for each item, go over c from its weight up to capacity	O(N · W)	O(W)

Why does this belong to this pattern?

Clues in the problem statement

“you may take the same item as many times as you like”Items can repeat, so this is the unbounded knapsack. The capacity loop goes low → high.
“total weight is at most the capacity”The bag has room c, so the table is indexed by capacity.
“biggest total value”Keep the best of the choices: skip the item, or add one more copy of it.

Choose items with repeats allowed+total weight ≤ capacity+maximize total value→DP — Knapsack, Unbounded (one row, capacity low → high)

This is the anchor of the unbounded sub-pattern. The only change from 0/1 knapsack is the loop direction. 0/1 goes capacity high → low, so each item is read from the old row and can be used once. Unbounded goes low → high, so the item can be read from the row it is building. Its neighbours keep this idea, but change what a cell means (Coin Change) or the loop order (Coin Change II and Combination Sum IV).

Don't make this mistake

Pattern confusion: the 0/1 loop (capacity high → low)

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

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

High → low makes dp[c − w] still hold the value from before this item, so each item is used at most once. On the dry run (A = weight 2 value 5, B = weight 3 value 7, capacity 7), the high → low loop gives dp[7] = 12, which is A once plus B once. The correct answer is 17: A twice plus B once.

Forgetting the max with the old value

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

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

Overwriting throws away the best value found so far. On the dry run, item B at capacity 4 would replace dp[4] = 10 with 7, and the final answer would be 14 instead of 17.

Starting the inner loop at 0

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

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

For any c smaller than the weight, c − wt[i] is negative, so the code reads before the start of the array. Start at the item's weight.

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