算法练习(24) - 动态规划:最大效益

问题

Serling 公司购买长钢条,将其切割为短钢条出售. 切割工序本身没有成本支出.公司管理层希望知道最佳的切割方案.假定我们知道Serling公司出售一段长为i的钢条价格为p_i(i=1,2,...,) 钢条的长度为整英寸,以下为价格表的样例

长度i	1	2	3	4	5	6	7	8	9	10
价格p_i	1	5	8	9	10	17	17	20	24	30

给定一段长度为n 的钢条和一个价格表p_i(i= 1,2,...,n),求切割方案,使得销售收益r_n最大.

code

public class _04DynamicProgrammingTest {

    @Test
    public void dynamicProgramming_Test() {
        int[]  len = {1,2,3,4,5,6,7,8,9,10};
        int[]  p = {1,5,8,9,10,17,17,20,24,30};
        int n = 7;
        int i = this.dynamicProgramming(n, p);
        System.out.println(i);

    }

    private int dynamicProgramming(int n, int[] p) {
        int[] r = new int[n + 1];
        Arrays.fill(r,0);
        for (int j = 1; j <= n; j++) {
            int q = -1;
            for (int i = 1; i <= j; i++) {
                q = Math.max(q,p[i-1] + r[j-i]);
            }
            r[j] = q;
        }
        return r[n];
    }
}

思路

将一个大问题,划分为同性质的小问题(外层循环),将小问题划分为从底到上的解答过程(内层循环)
重点理解:

...
for (int i = 1; i <= j; i++) {
       q = Math.max(q,p[i-1] + r[j-i]);
}
...

这段代码是一定有解的,原因是 j是从1递增上去的,在求解过程中,小问题的解已经缓存到了r[]数组中.
固此种解法也称为"自底向上"求解法;

复杂度

双重循环,O(n^2)