算法导论:钢条切割问题方法全解(递归+动态规划)

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        int[] p = {0,1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
//        System.out.println(main.CUT_ROD(p, 5));
//        System.out.println(main.MEMORIZED_CUT_ROD(p, 5));
//        System.out.println(main.BOTTOM_UP_CUT_ROD(p, 5));
        main.PRINT_CUT_ROD_SOLUTION(p,5);
    }

    //钢条切割问题:
//    自顶向下递归实现
    public int CUT_ROD(int p[], int n) {
        if (n==0) return 0;
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i] + CUT_ROD(p, n - i));
        }
        return q;
    }

    //    加入备忘机制的自顶向下递归实现
    public int MEMORIZED_CUT_ROD(int p[], int n) {
        int[] r = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            r[i] = Integer.MIN_VALUE;
        }
        return MEMORIZED_CUT_ROD_AUX(p, n, r);
    }
    public int MEMORIZED_CUT_ROD_AUX(int p[], int n,int r[]) {
        if (r[n]>=0) return r[n];
        if (n == 0) return 0;
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i] + CUT_ROD(p, n - i));
        }
        return q;
    }

    //  自底向上的循环实现
    public int BOTTOM_UP_CUT_ROD(int[] p, int n) {
        int[] r = new int[n + 1];
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                q = Math.max(q, r[j] + p[i - j]);
            }
            r[i] = q;
        }
        return q;
    }

    //    记录第一段钢条的切割长度
    class PROFIT_LENGTH{
        int profit[];
        int length[];
        public PROFIT_LENGTH(int c[], int s[]) {
            this.length = s;
            this.profit = c;
        }
    }
    public void PRINT_CUT_ROD_SOLUTION(int[] p, int n) {
        PROFIT_LENGTH res = EXTENDED_BOTTOM_UP_CUT_ROD(p, n);
        while (n > 0) {
            System.out.println(res.length[n]+" "+res.profit[n]);
            n = n - res.length[n];
        }
    }
    public PROFIT_LENGTH EXTENDED_BOTTOM_UP_CUT_ROD(int[] p, int n) {
        int[] r = new int[n + 1];
        int[] s = new int[n + 1];
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (q < r[j] + p[i - j]) {
                    q = r[j] + p[i - j];
                    r[i] = q;
                    s[i] = j==0?i:j;
                }
            }
        }
        return new PROFIT_LENGTH(r,s);
    }

    //15.1-3考虑成本cost
    public int BOTTOM_UP_CUT_ROD_COST(int[] p, int n,int cost) {
        int[] r = new int[n + 1];
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                int curr = q == 0 ? r[j] + p[i - j] : r[j] + p[i - j] + cost;
                if (q < curr) {
                    q = curr;
                    r[i] = q;
                }
            }
        }
        return q;
    }
}