算法练习(24) - 动态规划:最大效益
问题
Serling 公司购买长钢条,将其切割为短钢条出售. 切割工序本身没有成本支出.公司管理层希望知道最佳的切割方案.假定我们知道Serling公司出售一段长为i的钢条价格为p_i(i=1,2,...,) 钢条的长度为整英寸,以下为价格表的样例
长度iii | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
价格pip_ipi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
给定一段长度为nnn 的钢条和一个价格表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)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
