Definition
- Unbounded Knapsack mapping – the rod length is the capacity, each available cut length is an item with its length as weight and its price as value, and items are reusable.
- 1D DP array – dp[c] holds the maximum revenue for a rod of total length c, with dp[0] = 0.
- Upward sweep – for each available length, sweep capacity from that length up to N so the same length can be reused multiple times.
- Recurrence – dp[c] = max(dp[c], price[len] + dp[c - len]) for each available length len.
- Cut reconstruction – a parallel array records which length improved each capacity, allowing you to trace the actual cuts.
The National Bank of India holds a fixed-term deposit of a certain duration and can break it into sub-terms, each paying a known interest rate. The bank wants to split the term to maximize total interest, reusing the most profitable sub-term length as often as it fits. Rod Cutting models this optimization.
Understanding the Concepts
What is the Rod Cutting problem?
Given a rod of length N and a price list where price[i] is the revenue for selling a piece of length i, cut the rod into pieces to maximize total revenue. Each length can be used any number of times. This is a classic dynamic programming problem that maps directly to the Unbounded Knapsack pattern.
package com.bank.investment;
public class RodCutting {
public static int maxRevenue(int[] prices, int rodLength) {
int[] dp = new int[rodLength + 1];
// dp[0] = 0: rod of length 0 yields 0 revenue
for (int len = 1; len <= prices.length; len++) {
for (int c = len; c <= rodLength; c++) {
dp[c] = Math.max(dp[c], prices[len - 1] + dp[c - len]);
}
}
return dp[rodLength];
}
}
Why is this an Unbounded Knapsack problem?
In the Unbounded Knapsack, you have a capacity (the rod length), items with weight and value (each cut length with its length as weight and its price as value), and each item can be used unlimited times. The rod can contain multiple pieces of the same length, which is the defining characteristic of the unbounded variant. The upward sweep from len to N is what enables reuse of the same length.
// Unbounded Knapsack mapping:
// Capacity = rod length N
// Items = available cut lengths 1, 2, ..., N
// Item weight = cut length
// Item value = price for that length
// Reuse = same length can appear multiple times (upward sweep)
How does the upward sweep enable reuse?
In the 0/1 Knapsack, you sweep capacity downward so each item is used at most once. In the Unbounded Knapsack, you sweep upward. When computing dp[c], dp[c - len] may already include a piece of the same length from this iteration, effectively allowing that length to be used again.
package com.bank.investment;
public class UpwardSweepDemo {
public static void trace() {
int[] prices = {2, 5, 9}; // lengths 1, 2, 3
int rodLength = 6;
int[] dp = new int[7]; // dp[0..6]
// Processing length 3 (price 9):
// dp[3] = max(dp[3], 9 + dp[0]) = 9
// dp[6] = max(dp[6], 9 + dp[3]) = 9 + 9 = 18
// dp[3] was updated earlier in THIS sweep, so length 3 is reused!
// Rod of length 6 = two pieces of length 3, revenue = 18
System.out.println("Max revenue for rod 6: " + RodCutting.maxRevenue(prices, rodLength));
}
}
Max revenue for rod 6: 18
How do you reconstruct the actual cuts?
To know which lengths were chosen, maintain a parallel array that records which length improved each capacity. After computing dp[N], trace back from N by subtracting the recorded length at each step until you reach zero.
package com.bank.investment;
import java.util.ArrayList;
import java.util.List;
public class RodCuttingWithPlan {
public static List<Integer> maxRevenueWithCuts(int[] prices, int rodLength) {
int[] dp = new int[rodLength + 1];
int[] cutUsed = new int[rodLength + 1]; // which length improved each capacity
for (int len = 1; len <= prices.length; len++) {
for (int c = len; c <= rodLength; c++) {
int candidate = prices[len - 1] + dp[c - len];
if (candidate > dp[c]) {
dp[c] = candidate;
cutUsed[c] = len;
}
}
}
// Reconstruct cuts
List<Integer> cuts = new ArrayList<>();
int remaining = rodLength;
while (remaining > 0) {
cuts.add(cutUsed[remaining]);
remaining -= cutUsed[remaining];
}
System.out.println("Max revenue: " + dp[rodLength]);
System.out.println("Cut plan: " + cuts);
return cuts;
}
public static void main(String[] args) {
int[] prices = {2, 5, 9};
maxRevenueWithCuts(prices, 6);
}
}
Max revenue: 18
Cut plan: [3, 3]
What is the time and space complexity?
| Aspect | Complexity | Notes |
|---|---|---|
| Time | O(N * L) | N = rod length, L = number of available lengths |
| Space | O(N) | 1D DP array |
| With reconstruction | O(N) extra | Parallel cutUsed array |
What are edge cases?
Edge cases include a rod of length zero (revenue is zero), a single available length, and prices where selling the rod uncut is more profitable than any combination of cuts.
package com.bank.investment;
public class EdgeCases {
public static void test() {
// Rod length 0: no cuts possible, revenue = 0
System.out.println(RodCutting.maxRevenue(new int[]{5}, 0)); // 0
// Single length: price[1]=3, rod=5 → 5 pieces of length 1 = 15
System.out.println(RodCutting.maxRevenue(new int[]{3}, 5)); // 15
// Uncut is best: prices = [1, 5, 6, 10], rod=4 → uncut length 4 = 10
System.out.println(RodCutting.maxRevenue(new int[]{1, 5, 6, 10}, 4)); // 10
}
}
0
15
10
What are common mistakes?
The most common mistake is sweeping capacity downward (as in 0/1 Knapsack), which prevents reusing the same length. Another mistake is using a 0-indexed price array without adjusting for 1-indexed lengths.
package com.bank.investment;
public class CommonMistakes {
// WRONG: downward sweep (0/1 Knapsack style) - prevents reuse
public static int wrongVersion(int[] prices, int rodLength) {
int[] dp = new int[rodLength + 1];
for (int len = 1; len <= prices.length; len++) {
for (int c = rodLength; c >= len; c--) { // BUG: downward sweep!
dp[c] = Math.max(dp[c], prices[len - 1] + dp[c - len]);
}
}
return dp[rodLength]; // Returns suboptimal result: each length used at most once
}
// CORRECT: upward sweep allows reuse
public static int correctVersion(int[] prices, int rodLength) {
int[] dp = new int[rodLength + 1];
for (int len = 1; len <= prices.length; len++) {
for (int c = len; c <= rodLength; c++) { // upward sweep!
dp[c] = Math.max(dp[c], prices[len - 1] + dp[c - len]);
}
}
return dp[rodLength];
}
}
How is this used in banking?
At the National Bank of India, Rajesh used this to split a fixed-term deposit into sub-terms to maximize total interest. Each sub-term length has a known interest rate, and the same sub-term can be reused as often as it fits within the total term. The DP finds the optimal split, and the cut reconstruction tells the customer exactly which sub-terms to choose.
package com.bank.investment;
import java.math.BigDecimal;
public class TermDepositOptimizer {
public static void optimize() {
// Sub-term interest rates (for lengths 1, 2, 3 years)
// Length 1: 5% of principal
// Length 2: 12% of principal
// Length 3: 20% of principal
int[] interestBasisPoints = {500, 1200, 2000};
int totalTerm = 6; // 6 years
// Rod Cutting: maximize total interest
// Optimal: two 3-year sub-terms = 20% + 20% = 40%
System.out.println("Optimal split for 6-year deposit:");
RodCuttingWithPlan.maxRevenueWithCuts(interestBasisPoints, totalTerm);
}
}
Optimal split for 6-year deposit:
Max revenue: 4000
Cut plan: [3, 3]
Visual Overview
Rod Cutting DP Table
=====================
Prices: length 1 = 2, length 2 = 5, length 3 = 9
Rod length N = 6
dp[0]=0 dp[1]=0 dp[2]=0 dp[3]=0 dp[4]=0 dp[5]=0 dp[6]=0
Processing length 1 (price 2):
dp[1] = max(0, 2+dp[0]) = 2
dp[2] = max(0, 2+dp[1]) = 4
dp[3] = max(0, 2+dp[2]) = 6
dp[4] = max(0, 2+dp[3]) = 8
dp[5] = max(0, 2+dp[4]) = 10
dp[6] = max(0, 2+dp[5]) = 12
Processing length 2 (price 5):
dp[2] = max(4, 5+dp[0]) = 5
dp[3] = max(6, 5+dp[1]) = 7
dp[4] = max(8, 5+dp[2]) = 10
dp[5] = max(10, 5+dp[3]) = 12
dp[6] = max(12, 5+dp[4]) = 15
Processing length 3 (price 9):
dp[3] = max(7, 9+dp[0]) = 9
dp[4] = max(10, 9+dp[1]) = 11
dp[5] = max(12, 9+dp[2]) = 14
dp[6] = max(15, 9+dp[3]) = 18 ← two length-3 pieces!
Answer: dp[6] = 18
Upward vs Downward Sweep
=========================
Upward (c = len → N): dp[c-len] may already include this length
→ same length REUSED (Unbounded)
Downward (c = N → len): dp[c-len] is from previous iteration
→ each length used ONCE (0/1)
Rod Cutting needs Unbounded → use upward sweep
Key Takeaway
Rod Cutting is an Unbounded Knapsack problem where the rod length is the capacity and each available cut length is a reusable item with its price as the value. The 1D DP array dp[c] holds the maximum revenue for a rod of length c, and the upward sweep from each length to N is what allows the same length to be used multiple times. When dp[c] is computed, dp[c - len] may already include a piece of the same length from the current iteration, effectively reusing it.
The recurrence is dp[c] = max(dp[c], price[len] + dp[c - len]) for each available length. After filling the array, dp[N] is the answer. To reconstruct the actual cuts, maintain a parallel array that records which length improved each capacity, then trace back from N by subtracting the recorded length at each step.
At the National Bank of India, Rajesh used this to split fixed-term deposits into sub-terms to maximize total interest. Each sub-term length had a known interest rate, and the same sub-term could be reused as often as it fit within the total term. The DP found the optimal split, and the cut reconstruction told the customer exactly which sub-terms to choose.
The critical implementation detail is the sweep direction: upward for unbounded (reuse allowed), downward for 0/1 (each item used once). Confusing the two produces a suboptimal result that is hard to debug because it still returns a valid but non-optimal answer.
Remember one sentence: sweep capacity upward from each cut length to N so the same length can be reused, and dp[N] gives the maximum revenue.
---