Definition
- Unbounded Knapsack count variant – each allowed length is a reusable item, and the objective is to maximize the count of pieces rather than their total value.
- Sentinel initialization – every dp[len] starts at Integer.MIN_VALUE (unreachable), except dp[0] = 0 (zero pieces form zero length).
- Reachability guard – only extend from dp[len - cut] when it is not the sentinel, preventing impossible cuts from being counted.
- Recurrence – dp[len] = max(dp[len], 1 + dp[len - cut]) for each allowed cut that fits and has a reachable remainder.
- Impossible case – if dp[N] is still the sentinel, return -1 because no combination of allowed lengths sums to N exactly.
The National Bank of India issues a cheque book strip of a fixed length and wants to cut it into the largest number of valid cheque segments. Only certain segment lengths are permitted, and each can be reused. Maximum Ribbon Cut computes that largest piece count, or reports that an exact cut is impossible.
Understanding the Concepts
What is the Maximum Ribbon Cut problem?
Given a ribbon of length N and a set of allowed cut lengths, cut the ribbon into the maximum number of pieces where each piece must be one of the allowed lengths. Each allowed length can be used unlimited times. If the ribbon cannot be cut exactly using the allowed lengths, return -1.
package com.bank.cheque;
public class MaximumRibbonCut {
public static int maxPieces(int ribbonLength, int[] allowedLengths) {
int[] dp = new int[ribbonLength + 1];
java.util.Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int len = 1; len <= ribbonLength; len++) {
for (int cut : allowedLengths) {
if (cut <= len && dp[len - cut] != Integer.MIN_VALUE) {
dp[len] = Math.max(dp[len], 1 + dp[len - cut]);
}
}
}
return dp[ribbonLength] == Integer.MIN_VALUE ? -1 : dp[ribbonLength];
}
}
Why is this the maximization sibling of Minimum Coin Change?
Minimum Coin Change asks for the fewest coins that sum to a target. Maximum Ribbon Cut asks for the most pieces that sum to a length. Both use an unbounded supply and a sentinel for unreachable values, but one minimizes and the other maximizes. The sentinel and reachability guard are shared mechanics; only the optimization direction differs.
// Minimum Coin Change: dp[len] = min(dp[len], 1 + dp[len - coin])
// Sentinel: Integer.MAX_VALUE (unreachable = infinitely expensive)
// Answer: dp[target] or -1 if still sentinel
// Maximum Ribbon Cut: dp[len] = max(dp[len], 1 + dp[len - cut])
// Sentinel: Integer.MIN_VALUE (unreachable = impossible)
// Answer: dp[N] or -1 if still sentinel
How does the reachability guard work?
Before extending from dp[len - cut], you must check that dp[len - cut] is not the sentinel. If it is the sentinel, that remainder length is unreachable, and building on it would count an impossible cut. The guard dp[len - cut] != Integer.MIN_VALUE ensures you only extend from valid states.
package com.bank.cheque;
public class ReachabilityDemo {
public static void trace() {
int ribbonLength = 7;
int[] cuts = {3, 5};
// dp[0]=0, dp[1]=MIN, dp[2]=MIN (unreachable with 3 and 5)
// dp[3] = max(MIN, 1+dp[0]) = 1 (one piece of length 3)
// dp[4] = check dp[1] for cut=3: MIN → skip
// check dp[-1]: skip (cut=5 too big)
// dp[4] = MIN (unreachable!)
// dp[5] = max(MIN, 1+dp[2]=MIN → skip, 1+dp[0]=1) = 1
// dp[6] = max(MIN, 1+dp[3]=2) = 2 (two pieces of length 3)
// dp[7] = check dp[4]=MIN → skip for cut=3
// check dp[2]=MIN → skip for cut=5
// dp[7] = MIN → return -1!
System.out.println("Ribbon 7 with cuts [3,5]: " +
MaximumRibbonCut.maxPieces(7, cuts)); // -1
}
}
Ribbon 7 with cuts [3,5]: -1
How does the DP table fill step by step?
For a ribbon of length 9 with allowed cuts [2, 3, 5], the DP fills as follows:
package com.bank.cheque;
public class DPTrace {
public static void trace() {
int[] cuts = {2, 3, 5};
int n = 9;
// dp[0]=0
// dp[1]=MIN (no cut fits)
// dp[2]=max(MIN, 1+dp[0])=1 (one piece of 2)
// dp[3]=max(MIN, 1+dp[1]=skip, 1+dp[0]=1)=1 (one piece of 3)
// dp[4]=max(MIN, 1+dp[2]=2)=2 (two pieces of 2)
// dp[5]=max(MIN, 1+dp[3]=2, 1+dp[2]=2, 1+dp[0]=1)=2
// Wait: cut=5 gives 1+dp[0]=1, cut=2 gives 1+dp[3]=2, cut=3 gives 1+dp[2]=2
// dp[5]=2 (e.g., pieces of 2+3)
// dp[6]=max(1+dp[4]=3, 1+dp[3]=2, 1+dp[1]=skip)=3 (three pieces of 2)
// dp[7]=max(1+dp[5]=3, 1+dp[4]=3, 1+dp[2]=2)=3
// dp[8]=max(1+dp[6]=4, 1+dp[5]=3, 1+dp[3]=2)=4 (four pieces of 2)
// dp[9]=max(1+dp[7]=4, 1+dp[6]=4, 1+dp[4]=3)=4
System.out.println("Max pieces for ribbon 9: " +
MaximumRibbonCut.maxPieces(9, cuts)); // 4
}
}
Max pieces for ribbon 9: 4
What happens when the ribbon cannot be cut exactly?
If no combination of allowed lengths sums to exactly N, dp[N] remains at the sentinel value Integer.MIN_VALUE. In that case, return -1 to indicate impossibility. This is the same pattern as Minimum Coin Change returning -1 when no coin combination reaches the target.
package com.bank.cheque;
public class ImpossibleCase {
public static void test() {
// Ribbon length 7, allowed cuts [4, 6]
// dp[4]=1, dp[6]=1, dp[8]=2, but dp[7]=MIN
// No way to combine 4s and 6s to make exactly 7
System.out.println(MaximumRibbonCut.maxPieces(7, new int[]{4, 6})); // -1
// Ribbon length 0: trivially 0 pieces
System.out.println(MaximumRibbonCut.maxPieces(0, new int[]{3, 5})); // 0
}
}
-1
0
What is the time and space complexity?
| Aspect | Complexity | Notes |
|---|---|---|
| Time | O(N * C) | N = ribbon length, C = number of allowed cuts |
| Space | O(N) | 1D DP array |
What are common mistakes?
The most common mistake is initializing dp to all zeros instead of a negative sentinel. Without the sentinel, you cannot distinguish between a reachable length with zero pieces and an unreachable length. Another mistake is skipping the reachability guard, which lets you build on unreachable states and count impossible cuts.
package com.bank.cheque;
public class CommonMistakes {
// WRONG: initialize dp to 0 instead of sentinel
public static int wrongVersion(int n, int[] cuts) {
int[] dp = new int[n + 1]; // all zeros!
for (int len = 1; len <= n; len++) {
for (int cut : cuts) {
if (cut <= len) {
dp[len] = Math.max(dp[len], 1 + dp[len - cut]);
// BUG: dp[len-cut] might be 0 for an unreachable length
// This counts impossible cuts as if they were possible!
}
}
}
return dp[n]; // Returns wrong positive result for impossible cases
}
// CORRECT: sentinel + reachability guard
// See MaximumRibbonCut.maxPieces above
}
How is this used in banking?
At the National Bank of India, the cheque book department cuts strips into the maximum number of valid cheque segments. Only certain segment lengths are approved (regulatory requirement), and each length can be reused. The department needs to know if a strip can be cut exactly, and if so, what is the maximum number of segments.
package com.bank.cheque;
public class ChequeStripCutter {
public static void main(String[] args) {
int stripLength = 12;
int[] approvedSegments = {3, 5};
int maxSegments = MaximumRibbonCut.maxPieces(stripLength, approvedSegments);
if (maxSegments == -1) {
System.out.println("Strip of length " + stripLength + " cannot be cut exactly.");
} else {
System.out.println("Maximum segments from strip " + stripLength + ": " + maxSegments);
}
}
}
Maximum segments from strip 12: 4
Visual Overview
DP Table Fill
==============
Ribbon: 9 Allowed cuts: [2, 3, 5]
Sentinel: MIN = unreachable
len: 0 1 2 3 4 5 6 7 8 9
dp: [0] [MIN] [1] [1] [2] [2] [3] [3] [4] [4]
dp[0]=0 (base case)
dp[2]=1 (one piece of 2)
dp[3]=1 (one piece of 3)
dp[4]=2 (two pieces of 2)
dp[6]=3 (three pieces of 2)
dp[9]=4 (e.g., four pieces: 2+2+2+3)
Reachability Guard
===================
To compute dp[7]:
cut=2: dp[5]=2 (reachable) → 1+2=3 ✓
cut=3: dp[4]=2 (reachable) → 1+2=3 ✓
cut=5: dp[2]=1 (reachable) → 1+1=2 ✓
dp[7] = max(3, 3, 2) = 3
To compute dp[1]:
cut=2: 2>1, skip
cut=3: 3>1, skip
cut=5: 5>1, skip
dp[1] = MIN (unreachable!)
Comparison: Max vs Min
=======================
┌────────────────────────────┬─────────────────────────────┐
│ Minimum Coin Change │ Maximum Ribbon Cut │
├────────────────────────────┼─────────────────────────────┤
│ Minimize count │ Maximize count │
│ Sentinel: MAX_VALUE │ Sentinel: MIN_VALUE │
│ dp = min(dp, 1+dp[r]) │ dp = max(dp, 1+dp[r]) │
│ Same reachability guard │ Same reachability guard │
│ Return -1 if sentinel │ Return -1 if sentinel │
└────────────────────────────┴─────────────────────────────┘
Key Takeaway
Maximum Ribbon Cut is the maximization-count variant of the Unbounded Knapsack pattern. You keep a DP array where each slot holds the maximum number of pieces that exactly form that length, initialized to a negative sentinel meaning unreachable, except dp[0] = 0 because zero length needs zero pieces. For each length, you try every allowed cut that fits and, only when the remainder is reachable, take one piece plus the best count for the remainder.
The reachability guard is the critical detail: you must not build on an unreachable remainder, because that would count an impossible cut as valid. Without the guard, the algorithm reports positive results for ribbons that cannot actually be cut. After filling the table, if dp[N] is still the sentinel, you return -1 to indicate no exact cut exists.
At the National Bank of India, the cheque book department used this to cut strips into the maximum number of approved segments. Only certain segment lengths were permitted, and each could be reused. The department needed to know both whether a strip could be cut exactly and what the maximum segment count was.
This is the maximizing sibling of Minimum Coin Change: both use an unbounded supply and a sentinel, but one minimizes the count and the other maximizes it. Explaining that symmetry and the shared reachability guard is what shows depth.
Remember one sentence: maximize piece count with a sentinel-based DP that guards against unreachable remainders, and return -1 if dp[N] stays at the sentinel.
---