Problem Description

A company buys long steel rods and cuts them for sale. Cutting costs are negligible. Rod lengths are in inches. Given a price table $p$, where $p_{i}(i=1,2,\cdots,m)$ represents the price of a rod of length $i$ inches, find the cutting scheme that maximizes total revenue.

Problem Analysis

Assume the length of the long steel rod is $n$ inches. If the leftmost cut of the optimal scheme is $i$ inches long, we then solve for the optimal cutting scheme of the remaining $n-i$ inches. By considering all possible values for $i$, the maximum revenue $r_{n}$ corresponding to the best cutting scheme can be defined recursively:

C Code

There are two approaches to this problem:

(1) Divide and Conquer (Top-Down)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int Top_Down_Cut_Rod(int p[], int n){
    int r=0; // Maximum value
    int i;
    
    if(n==0){
        retrun 0;
    }
    
    for(i=1; i<=n; i++){
        int tmp = p[i]+Top_Down_Cut_Rod(p, n-i);
        r = (r>=tmp) ? r : tmp;
    }
    
    return r;
}

Time complexity $O(2^{n})$

(2) Dynamic Programming (Bottom-Up)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int Bottom_Up_Cut_Rod(int p[], int n, int *s){
    // *s: Optimal cutting method for subproblems
    int r[n+1]; // Optimal value for subproblems
    r[0]=0;
    
    for(int j=1; j<=n; j++){
        int tmp=0;
        for(int i=1; i<=j; i++){
            if(p[i]+r[j-1] > tmp){
                tmp = p[i]+r[j-i];
                s[j]=i;
            }
        }
        r[i]=tmp;
    }
    
    return r[n];
}

Time complexity $O(n^{2})$

Other Resources

Found an existing article during my search: 【基础算法】动态规划详解——钢条切割