Rod cutting & integer break

Overview

Both problems partition a whole into pieces and maximise something over the split. Rod cutting takes a length and a price table and asks for the most valuable way to cut it; integer break splits a number into at least two positive parts and maximises their product. The shared recurrence is: try every possible first piece, then add the already-computed optimum for the remainder. That single idea — first piece plus optimal remainder — is what makes the exponential space of all partitions collapse into an O(n^2) sweep.

Why it matters

Cutting stock is a real manufacturing problem: steel, cable, paper and timber are all bought in lengths and cut for orders, and the difference between a good and a naive split is direct revenue. The pattern also covers splitting a job into batches, choosing chunk sizes for transfers, and any decision of the form "pick a first piece, then solve the rest optimally".

Core concepts

First-piece decomposition. dp[len] = max over cut of (price[cut] + dp[len - cut]). Every partition has a first piece; enumerating it and reusing the optimum for the rest counts each partition exactly once, without ever listing them.

Unbounded by nature. A piece length may be reused freely, so dp[len - cut] may itself contain that same length. No downward sweep is needed — this is the unbounded shape, unlike the 0/1 knapsack.

Rod cutting base case. dp[0] = 0 — a rod of length zero is worth nothing.

Integer break's twist. The problem requires at least two parts, so n itself is not a valid answer. For each split point j, the piece j may be left whole or broken further, so the factor is max(j, dp[j]); the same choice applies to i - j. Taking dp[j] unconditionally would force an unnecessary extra break and understate the product.

Growth. Products grow quickly — int overflows for moderate n. Use long long or the specified modulus.

Complexity. O(n^2): for each length, try every first piece.

Syntax notes

#include <stdlib.h>

/* p[i] = price of a piece of length i+1 ; rod of length n */
int rod(const int *p, int n) {
    int *dp = calloc((size_t)n + 1, sizeof *dp);   /* dp[0] = 0 */
    if (!dp) return -1;
    for (int len = 1; len <= n; len++) {
        int best = 0;
        for (int cut = 1; cut <= len; cut++) {
            int cand = p[cut-1] + dp[len-cut];      /* first piece + optimal rest */
            if (cand > best) best = cand;
        }
        dp[len] = best;
    }
    int r = dp[n];
    free(dp);
    return r;
}

/* max product of at least two positive parts summing to n */
long long ibreak(int n) {
    long long *dp = calloc((size_t)n + 1, sizeof *dp);
    if (!dp) return -1;
    for (int i = 2; i <= n; i++) {
        long long best = 0;
        for (int j = 1; j < i; j++) {
            long long f1 = (j > dp[j]) ? j : dp[j];            /* keep whole or break */
            long long f2 = ((i-j) > dp[i-j]) ? (i-j) : dp[i-j];
            if (f1 * f2 > best) best = f1 * f2;
        }
        dp[i] = best;
    }
    long long r = dp[n];
    free(dp);
    return r;
}

Key points:

• p[cut-1] because prices are 1-indexed by length while the array is 0-indexed.
• In ibreak, max(j, dp[j]) is essential — a part may be better left whole.
• Products need long long.

Lesson

Rod cutting maximizes revenue by choosing where to cut a rod given per-length prices; integer break maximizes the product of positive parts summing to n. Both build dp[i] from a best first split — and integer break adds the twist that each factor may be left whole or broken further.

Code examples

#include <stdio.h>
#include <stdlib.h>
static int rod(const int*p,int n){int*dp=calloc(n+1,sizeof(int));for(int len=1;len<=n;len++){int best=0;for(int c=1;c<=len;c++){int v=p[c-1]+dp[len-c];if(v>best)best=v;}dp[len]=best;}int r=dp[n];free(dp);return r;}
static int ibreak(int n){int*dp=calloc(n+1,sizeof(int));for(int i=2;i<=n;i++){int best=0;for(int j=1;j<i;j++){int f1=j>dp[j]?j:dp[j];int f2=(i-j)>dp[i-j]?(i-j):dp[i-j];int p=f1*f2;if(p>best)best=p;}dp[i]=best;}int r=dp[n];free(dp);return r;}
int main(void){
    int price[]={1,5,8,9,10,17,17,20};
    printf("max revenue cutting a rod of length 8 = %d\n", rod(price,8));
    printf("max product breaking 10 into parts = %d\n", ibreak(10));
    return 0;
}

Line by line

Common mistakes

Off-by-one between length and price index; forgetting a factor can stay unbroken.

Debugging tips

Compiler errors and warnings:

• warning: array subscript if you index p[cut] instead of p[cut-1].
• Silent overflow in ibreak when the accumulator is int.

Runtime symptoms:

• Rod value is too low. Off-by-one in the price index — p[cut-1] is the price of a piece of length cut.
• ibreak(n) returns n. You allowed the trivial one-part "split". The loop must start at i = 2 and j < i, so at least two parts always exist.
• ibreak is too small. You used dp[j] instead of max(j, dp[j]), forcing every part to be broken further.
• Products go negative. int overflow; use long long.
• Crash for n = 0 or n = 1. Both are edge cases: ibreak is undefined for n < 2; decide and document the return value.

Technique: verify against the standard table — prices {1,5,8,9,10,17,17,20} give dp[4] = 10 and dp[8] = 22; ibreak(10) = 36.

Memory safety

• Price-array length is a contract. rod reads p[0 .. n-1]; if the caller supplies fewer prices than n, every long cut reads out of bounds. Pass the price count explicitly and validate it.
• Off-by-one indexing. p[cut-1] is correct; p[cut] reads one past the end at cut == n. This is a genuine buffer overread, not just a wrong answer.
• Validate n before allocating and check calloc for NULL.
• Zero-initialisation matters — dp[0] must be 0 and every entry is read before all are written.
• Overflow. Products in ibreak grow exponentially in the number of parts; long long covers moderate n, but very large n needs a modulus or big integers.
• Free on every path.

Real-world uses

Concrete uses: Cutting stock for steel bars, cables, pipes and paper rolls, where a price or demand table drives the split. Deciding batch sizes for a production run. Splitting a data transfer into chunks with size-dependent overhead. The integer-break shape appears in optimisation puzzles and in reasoning about how to decompose a budget for maximum multiplicative effect.

Professional best practices:

Beginner:

• Write the index mapping (p[cut-1] for length cut) in a comment; it is the most common bug.
• Check your dp table against a small hand-computed example.

Intermediate:

• Record the chosen first piece per length if the caller needs the actual cut list, not just the revenue.
• Note this is the unbounded shape — no downward sweep — and contrast it deliberately with the 0/1 knapsack so the distinction sticks.
• Watch the accumulator width; multiplicative DPs overflow far sooner than additive ones.

Practice tasks

1. (Beginner) Rod cutting. Implement int rod(const int *p, int n). Example: prices {1,5,8,9,10,17,17,20}, n = 4 -> 10; n = 8 -> 22. Concepts: first-piece decomposition, 1-indexed prices.

2. (Beginner) Integer break. Implement long long ibreak(int n) requiring at least two parts. Example: ibreak(2) -> 1; ibreak(10) -> 36. Concepts: max(j, dp[j]), minimum part count.

3. (Intermediate) Report the cuts. Extend rod to print the actual piece lengths chosen. Hint: store the best first cut for each length and walk backwards. Concepts: DP reconstruction.

4. (Intermediate) Bounded pieces. Restrict each piece length to be used at most once and compare the result. Hint: this becomes the 0/1 shape — sweep downward. Concepts: bounded vs unbounded.

Summary

Rod cutting and integer break share one recurrence: try every possible first piece and add the already-computed optimum for the remainder, which counts every partition exactly once in O(n^2). Both are unbounded — a piece length may repeat — so no downward sweep is needed, in deliberate contrast to the 0/1 knapsack. Watch two details: prices are 1-indexed by length so the array access is p[cut-1], and integer break must take max(j, dp[j]) for each part because a part is sometimes best left whole. Use long long for products, and validate that the price array is at least as long as the rod.

Practice with these exercises

• Rod cutting
• Integer break