侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 102 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

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

惊羽
2022-03-21 / 0 评论 / 0 点赞 / 938 阅读 / 821 字
温馨提示:
本文为原创作品,感谢您喜欢~

问题

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

长度$i$12345678910
价格$p_i$1589101717202430

给定一段长度为$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)$

0
广告 广告

评论区