Definition
- Unbounded Knapsack – each item may be chosen unlimited times to maximise total value within a capacity.
- Upward sweep – capacity loops from low to high, so
dp[c - weight]may already include the current item, enabling reuse. - vs 0/1 Knapsack – the only code difference is the loop direction; downward = use once, upward = unlimited.
- Pattern family – covers coin change (count ways), rod cutting, and ribbon cutting.
- 2D form –
dp[i][c] = max(dp[i-1][c], profit[i] + dp[i][c - weight[i]])using the same row for inclusion. - Complexity – O(N * C) time and O(C) space.
The National Bank of India offers investment instruments that Rajesh can buy repeatedly: as many units of each as he likes, up to his budget. He wants the highest total return. Unbounded Knapsack decides the best return for each budget level while allowing the same instrument to be bought over and over.
Understanding the Concepts
What is Unbounded Knapsack?
Unbounded Knapsack is a variant of the knapsack problem where each item can be chosen any number of times. Given N items, each with a weight and a value, and a knapsack with capacity C, the goal is to maximise the total value by selecting items with repetition allowed.
The key difference from 0/1 Knapsack is that including an item does not consume it. After adding one copy of item i, you can still add another copy of the same item if there is remaining capacity.
package com.bank.dsa;
public class UnboundedKnapsack {
public static int maxProfit(int[] weight, int[] profit, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int c = weight[i]; c <= capacity; c++) { // upward sweep
dp[c] = Math.max(dp[c], profit[i] + dp[c - weight[i]]);
}
}
return dp[capacity];
}
public static void main(String[] args) {
int[] w = {1, 3, 4, 5};
int[] v = {2, 7, 8, 13};
System.out.println("Max profit: " + maxProfit(w, v, 10));
}
}
Max profit: 26
Why does the capacity loop run upward?
The upward sweep is what enables item reuse. When we compute dp[c], we read dp[c - weight[i]]. If that cell was already updated during the current item's pass, it may include one or more copies of item i. This is exactly what we want: unlimited copies.
In 0/1 Knapsack, the downward sweep ensures dp[c - weight[i]] has not been touched yet for the current item, so each item is used at most once. The loop direction is the single toggle between use-once and use-unlimited.
package com.bank.dsa;
public class SweepComparison {
// 0/1: downward sweep, each item once
public static int knapsack01(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i < w.length; i++)
for (int c = cap; c >= w[i]; c--) // downward
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
return dp[cap];
}
// Unbounded: upward sweep, unlimited copies
public static int knapsackUnbounded(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i < w.length; i++)
for (int c = w[i]; c <= cap; c++) // upward
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
return dp[cap];
}
public static void main(String[] args) {
int[] w = {2, 3};
int[] v = {5, 7};
int cap = 8;
System.out.println("0/1: " + knapsack01(w, v, cap));
System.out.println("Unbounded: " + knapsackUnbounded(w, v, cap));
}
}
0/1: 12
Unbounded: 20
How is Unbounded Knapsack different from 0/1 Knapsack?
| Aspect | 0/1 Knapsack | Unbounded Knapsack |
|---|---|---|
| Item usage | Each item at most once | Each item unlimited times |
| 1D sweep direction | High to low (downward) | Low to high (upward) |
| dp[c - w] meaning | Previous item's value | Current item's value (may include reuse) |
| 2D recurrence row | dp[i-1][c - w] (previous row) | dp[i][c - w] (same row) |
| Example problem | Pick loan deals (once) | Buy investment units (repeat) |
| Pattern family | Subset sum, partition | Coin change, rod cutting |
How does the 2D form look?
In the 2D version, the difference is even clearer. For 0/1 Knapsack, inclusion reads from the previous row dp[i-1]. For Unbounded Knapsack, inclusion reads from the current row dp[i], because the item remains available.
package com.bank.dsa;
public class UnboundedKnapsack2D {
public static int maxProfit(int[] weight, int[] profit, int capacity) {
int n = weight.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= capacity; c++) {
dp[i][c] = dp[i - 1][c]; // exclude
if (weight[i - 1] <= c) {
// include: read from SAME row dp[i], not dp[i-1]
dp[i][c] = Math.max(dp[i][c],
profit[i - 1] + dp[i][c - weight[i - 1]]);
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{1, 3, 4, 5}, new int[]{2, 7, 8, 13}, 10));
}
}
26
What are the problems in the Unbounded Knapsack pattern?
Several classic problems reduce to Unbounded Knapsack:
- Coin Change (min coins): minimise the number of coins to make an amount.
- Coin Change (count ways): count the distinct ways to make an amount.
- Rod Cutting: cut a rod into pieces to maximise profit, where each length has a price.
- Ribbon Cutting: cut a ribbon into pieces of given lengths to maximise the number of pieces.
package com.bank.dsa;
public class RodCutting {
public static int maxProfit(int[] prices, int length) {
int[] dp = new int[length + 1];
for (int i = 0; i < prices.length; i++) {
int pieceLen = i + 1;
for (int l = pieceLen; l <= length; l++) { // upward: same piece can repeat
dp[l] = Math.max(dp[l], prices[i] + dp[l - pieceLen]);
}
}
return dp[length];
}
public static void main(String[] args) {
int[] prices = {2, 6, 7, 10, 13};
System.out.println("Max rod profit: " + maxProfit(prices, 5));
}
}
Max rod profit: 14
What are common mistakes?
The most common mistake is using the wrong sweep direction. If you sweep downward for an unbounded problem, you get the 0/1 answer, which is typically smaller because items cannot repeat.
// WRONG: downward sweep for unbounded problem gives 0/1 answer
for (int c = cap; c >= w[i]; c--)
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]); // item used only once
// CORRECT: upward sweep allows unlimited copies
for (int c = w[i]; c <= cap; c++)
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]); // item reusable
Another mistake is confusing the loop order for counting problems versus maximisation problems. For counting the number of ways to make an amount (combinations not permutations), the item loop must be outer and the capacity loop inner.
What are the edge cases?
When all items weigh more than the capacity, the answer is zero. When the capacity is zero, the answer is zero. When there is one item of weight 1, it fills the entire capacity.
package com.bank.dsa;
public class UnboundedEdgeCases {
public static void main(String[] args) {
System.out.println(UnboundedKnapsack.maxProfit(new int[]{10}, new int[]{5}, 3)); // 0
System.out.println(UnboundedKnapsack.maxProfit(new int[]{1}, new int[]{3}, 5)); // 15
System.out.println(UnboundedKnapsack.maxProfit(new int[]{}, new int[]{}, 10)); // 0
}
}
0
15
0
When should you use Unbounded Knapsack in banking?
At the National Bank of India, this pattern applies to instruments that can be purchased in multiple units. Rajesh can buy as many units of a mutual fund or government bond as he likes within his budget. The advisory engine runs the unbounded knapsack DP to find the combination of instruments that maximises expected return.
package com.bank.service;
import java.math.BigDecimal;
public class InvestmentAdvisor {
public static BigDecimal bestReturn(int[] unitCost, BigDecimal[] unitReturn, int budget) {
BigDecimal[] dp = new BigDecimal[budget + 1];
for (int c = 0; c <= budget; c++) dp[c] = BigDecimal.ZERO;
for (int i = 0; i < unitCost.length; i++) {
for (int c = unitCost[i]; c <= budget; c++) { // upward: buy multiple units
BigDecimal candidate = unitReturn[i].add(dp[c - unitCost[i]]);
if (candidate.compareTo(dp[c]) > 0) dp[c] = candidate;
}
}
return dp[budget];
}
public static void main(String[] args) {
int[] costs = {5, 10, 15};
BigDecimal[] returns = {bd("1.2"), bd("3.5"), bd("4.0")};
System.out.println("Best return for budget 30: " + bestReturn(costs, returns, 30));
}
private static BigDecimal bd(String s) { return new BigDecimal(s); }
}
Best return for budget 30: 10.5
What should a senior engineer know?
A senior engineer should understand that the loop direction is the correctness lever, not a style choice. Being able to explain why upward enables reuse and downward prevents it is the single most important detail in knapsack problems.
The 2D form makes the difference even more explicit: 0/1 reads dp[i-1][c - w] (previous row), unbounded reads dp[i][c - w] (same row). This is the formal definition of the difference.
For maximisation problems, the loop order (items outer, capacity inner) does not matter. But for counting problems, the order determines whether you count combinations or permutations. Items outer gives combinations; capacity outer gives permutations.
Visual Overview
0/1 vs Unbounded Knapsack: Sweep Direction ─────────────────────────────────────────── 0/1 Knapsack (each item once): ┌─────────────────────────────────┐ │ for each item: │ │ c = capacity → weight[i] │ │ dp[c] = max(dp[c], v+dp[c-w]) │ │ ◄──── sweep direction ◄──── │ │ dp[c-w] = OLD (previous item) │ └─────────────────────────────────┘ Unbounded Knapsack (unlimited copies): ┌─────────────────────────────────┐ │ for each item: │ │ c = weight[i] → capacity │ │ dp[c] = max(dp[c], v+dp[c-w]) │ │ ────► sweep direction ────► │ │ dp[c-w] = NEW (current item) │ └─────────────────────────────────┘
Key Takeaway
Unbounded Knapsack is the repetition variant of the knapsack problem, where each item can be chosen as many times as you like. The surprising part for many candidates is how little the code changes from 0/1 Knapsack. The single meaningful difference is the direction of the capacity sweep in the one-dimensional form.
In 0/1 Knapsack, the capacity loop runs from high to low so that dp[c - weight] holds the value from the previous item. In Unbounded Knapsack, the loop runs from low to high so that dp[c - weight] may already include a copy of the current item, which is what enables repetition. The loop direction is the correctness lever, not a stylistic choice.
At the National Bank of India, Rajesh used this in an advisory engine for instruments that customers could buy in unlimited units, each with a unit cost and a unit return, to maximise total return within a budget. The upward capacity sweep allowed the same instrument to be selected multiple times.
The pattern covers coin change, rod cutting, and ribbon cutting problems. A senior engineer knows that for counting problems the loop order (items outer vs capacity outer) determines combinations versus permutations, which is a separate but related subtlety.
Remember one sentence: Unbounded Knapsack is the same DP as 0/1 but with an upward capacity sweep that deliberately allows item reuse.
---