切割工序本身没有成本支出.公司管理层希望知道最佳的切割方案.假定我们知道Serling公司出售一段长为i的钢条价格为 钢条的长度为整英寸,以下为价格表的样例
长度iii 1 2...3 4 5 6 7 8 9 10
价格pip_ipi 1 5 8 9 10 17 17 20 24 30
给定一段长度为nnn 的钢条和一个价格表 ,求切割方案,使得销售收益 最大.
code...r[j-i]);
}
r[j] = q;
}
return r[n];
}
}
思路
将一个大问题,划分为同性质的小问题...(外层循环),将小问题划分为从底到上的解答过程(内层循环)
重点理解:
...
for (int i = 1; i <= j; i++) {
q = Math.max(q,p[i-1]...这段代码是一定有解的,原因是 j是从1递增上去的,在求解过程中,小问题的解已经缓存到了r[]数组中.
固此种解法也称为"自底向上"求解法;
复杂度
双重循环,
云服务器
即时通信 IM
ICP备案
云直播
实时音视频
