Unbounded Knapsack Pattern — Complete Interview Guide

The Unbounded Knapsack pattern is one of the most important Dynamic Programming patterns asked in coding interviews.

Unlike 0/1 Knapsack, here you can use an item multiple times.

This pattern appears in:

• Coin Change
• Rod Cutting
• Integer Break
• Minimum Coins
• Ribbon Cutting
• Perfect Squares
• Combination Sum
• Target Sum Variations

---

1. What is Unbounded Knapsack?

You are given:

• weights[]
• values[]
• a bag capacity W

You may take an item:

• 0 times
• 1 time
• multiple times

Goal:
Maximize total profit/value.

---

2. Difference Between 0/1 and Unbounded Knapsack

Feature	0/1 Knapsack	Unbounded Knapsack
Pick item once	✅	❌
Pick item multiple times	❌	✅
DP transition	dp[i-1]	dp[i]
Common use	Subset problems	Coin/Rod problems

---

3. Core Recurrence

For item i:

If we take it:

value[i] + solve(i, remainingWeight - weight[i])

Notice:

solve(i, ...)

NOT:

solve(i + 1, ...)

Because we can reuse the same item.

---

4. Generic Recursive Template

class Solution {

    public int knapsack(int[] wt, int[] val, int capacity) {
        return dfs(0, capacity, wt, val);
    }

    private int dfs(int index, int remaining,
                    int[] wt, int[] val) {

        if (index == wt.length || remaining == 0) {
            return 0;
        }

        int skip = dfs(index + 1, remaining, wt, val);

        int take = 0;

        if (wt[index] <= remaining) {
            take = val[index] +
                    dfs(index,
                        remaining - wt[index],
                        wt, val);
        }

        return Math.max(skip, take);
    }
}

Time Complexity:

O(2^N)

---

5. Memoization (Top-Down DP)

class Solution {

    Integer[][] dp;

    public int knapsack(int[] wt, int[] val, int capacity) {

        dp = new Integer[wt.length][capacity + 1];

        return dfs(0, capacity, wt, val);
    }

    private int dfs(int index,
                    int remaining,
                    int[] wt,
                    int[] val) {

        if (index == wt.length || remaining == 0) {
            return 0;
        }

        if (dp[index][remaining] != null) {
            return dp[index][remaining];
        }

        int skip = dfs(index + 1, remaining, wt, val);

        int take = 0;

        if (wt[index] <= remaining) {
            take = val[index] +
                    dfs(index,
                        remaining - wt[index],
                        wt, val);
        }

        return dp[index][remaining] =
                Math.max(skip, take);
    }
}

Complexity:

Time: O(N * W)
Space: O(N * W)

---

6. Bottom-Up DP

State

dp[i][w]
= max profit using first i items
with capacity w

---

Transition

If we take current item again:

take = value[i-1] + dp[i][w - weight[i-1]]

Notice:

dp[i]

not:

dp[i-1]

---

Code

class Solution {

    public int unboundedKnapsack(int[] wt,
                                 int[] val,
                                 int capacity) {

        int n = wt.length;

        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {

            for (int w = 0; w <= capacity; w++) {

                int skip = dp[i - 1][w];

                int take = 0;

                if (wt[i - 1] <= w) {
                    take = val[i - 1]
                            + dp[i][w - wt[i - 1]];
                }

                dp[i][w] = Math.max(skip, take);
            }
        }

        return dp[n][capacity];
    }
}

---

7. Space Optimized DP

class Solution {

    public int unboundedKnapsack(int[] wt,
                                 int[] val,
                                 int capacity) {

        int[] dp = new int[capacity + 1];

        for (int i = 0; i < wt.length; i++) {

            for (int w = wt[i];
                 w <= capacity;
                 w++) {

                dp[w] = Math.max(
                        dp[w],
                        val[i] + dp[w - wt[i]]
                );
            }
        }

        return dp[capacity];
    }
}

Complexity:

Time: O(N * W)
Space: O(W)

---

8. How to Identify Unbounded Knapsack

Look for these clues:

Keywords

• unlimited supply
• infinite transactions
• can reuse
• multiple times
• any number of times

Common Structures

• maximize/minimize
• combinations
• count ways
• repeated selection

---

9. Most Important Variations

---

A. Coin Change I (Minimum Coins)

Problem

Minimum coins needed to make amount.

---

Transition

dp[amount] =
1 + dp[amount - coin]

---

Code

class Solution {

    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount + 1];

        Arrays.fill(dp, amount + 1);

        dp[0] = 0;

        for (int coin : coins) {

            for (int a = coin;
                 a <= amount;
                 a++) {

                dp[a] = Math.min(
                        dp[a],
                        1 + dp[a - coin]
                );
            }
        }

        return dp[amount] > amount
                ? -1
                : dp[amount];
    }
}

---

B. Coin Change II (Count Combinations)

Problem

Count total ways to form amount.

---

Code

class Solution {

    public int change(int amount, int[] coins) {

        int[] dp = new int[amount + 1];

        dp[0] = 1;

        for (int coin : coins) {

            for (int a = coin;
                 a <= amount;
                 a++) {

                dp[a] += dp[a - coin];
            }
        }

        return dp[amount];
    }
}

---

C. Rod Cutting Problem

Idea

Cut rod into pieces to maximize profit.

---

Mapping

Rod Cutting	Knapsack
rod length	capacity
piece size	weight
piece profit	value

---

Code

class Solution {

    public int cutRod(int[] price, int n) {

        int[] dp = new int[n + 1];

        for (int len = 1; len <= n; len++) {

            for (int cut = 1;
                 cut <= len;
                 cut++) {

                dp[len] = Math.max(
                        dp[len],
                        price[cut - 1]
                                + dp[len - cut]
                );
            }
        }

        return dp[n];
    }
}

---

D. Integer Break

Problem

Break integer into parts for maximum product.

---

Code

class Solution {

    public int integerBreak(int n) {

        int[] dp = new int[n + 1];

        dp[1] = 1;

        for (int num = 2; num <= n; num++) {

            for (int cut = 1; cut < num; cut++) {

                dp[num] = Math.max(
                        dp[num],
                        Math.max(
                                cut * (num - cut),
                                cut * dp[num - cut]
                        )
                );
            }
        }

        return dp[n];
    }
}

---

E. Perfect Squares

Problem

Minimum perfect squares summing to n.

---

Code

class Solution {

    public int numSquares(int n) {

        int[] dp = new int[n + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int i = 1; i * i <= n; i++) {

            int square = i * i;

            for (int j = square;
                 j <= n;
                 j++) {

                dp[j] = Math.min(
                        dp[j],
                        1 + dp[j - square]
                );
            }
        }

        return dp[n];
    }
}

---

F. Maximum Ribbon Cut

Problem

Maximum pieces from ribbon lengths.

---

Code

class Solution {

    public int maxCuts(int[] ribbonLengths,
                       int total) {

        int[] dp = new int[total + 1];

        Arrays.fill(dp, -1);

        dp[0] = 0;

        for (int ribbon : ribbonLengths) {

            for (int len = ribbon;
                 len <= total;
                 len++) {

                if (dp[len - ribbon] != -1) {

                    dp[len] = Math.max(
                            dp[len],
                            1 + dp[len - ribbon]
                    );
                }
            }
        }

        return dp[total];
    }
}

---

10. Pattern Recognition Cheat Sheet

Problem Type	Goal
Maximum profit	Use Math.max
Minimum coins	Use Math.min
Count ways	Use addition
Exact fill	Use INF or -1
Reuse allowed	Unbounded

---

11. Important DP Loop Direction

Unbounded Knapsack

for (int w = weight;
     w <= capacity;
     w++)

FORWARD traversal.

---

0/1 Knapsack

for (int w = capacity;
     w >= weight;
     w--)

BACKWARD traversal.

---

12. Top Interview Questions

Beginner

1. Coin Change
2. Coin Change II
3. Rod Cutting
4. Integer Break
5. Perfect Squares

---

Medium

1. Combination Sum IV
2. Maximum Ribbon Cut
3. Minimum Cost for Tickets
4. Dice Roll Sum
5. Target Sum Variants

---

Advanced

1. Cutting Segments
2. Burst Balloons (DP interval relation)
3. Partition Array for Maximum Sum
4. Cherry Pickup variations
5. Unbounded Subsequence DP

---

13. Master Template

for (item : items) {

    for (capacity from itemWeight -> maxCapacity) {

        dp[capacity] =
                operation(
                        dp[capacity],
                        currentValue +
                        dp[capacity - itemWeight]
                );
    }
}

---

14. Common Mistakes

1. Using backward traversal

Wrong for unbounded problems.

---

2. Using dp[i-1]

Should often use:

dp[i]

because item reuse is allowed.

---

3. Confusing combinations vs permutations

Combination

coin outer loop
amount inner loop

Permutation

amount outer loop
coin inner loop

---

15. Interview Strategy

When you see:

• infinite supply
• reuse allowed
• minimum coins
• rod cutting
• count ways repeatedly

Think:

UNBOUNDED KNAPSACK

Then decide:

Goal	Operation
maximize	max
minimize	min
count ways	+

---

16. Final Revision Notes

Core Formula

dp[w] = \max(dp[w],\ value[i] + dp[w-weight[i]])

---

Loop Order

for item
    for capacity increasing

---

Complexity

Approach	Time	Space
Recursion	Exponential	O(N)
Memoization	O(NW)	O(NW)
Tabulation	O(NW)	O(NW)
Optimized	O(NW)	O(W)

---

17. Best Problems to Practice

Problem	Platform
Coin Change	LeetCode 322
Coin Change II	LeetCode 518
Rod Cutting	GFG
Integer Break	LeetCode 343
Perfect Squares	LeetCode 279
Combination Sum IV	LeetCode 377
Minimum Cost Tickets	LeetCode 983
Maximum Ribbon Cut	Educative/GFG