首页 > 其他 > 详细

[DP] Rod-cutting problem

时间:2014-06-10 16:43:10      阅读:464      评论:0      收藏:0      [点我收藏+]

给一个长度为 n 的杆子,切成小段卖出去,价格根据小段的长度不同而不同。下面是一个例子

bubuko.com,布布扣

我们要通过切成小段卖出尽可能高的总价钱。问题是:How to decompose the problem?

bubuko.com,布布扣

Decomposition 的第一步是:第一刀切在哪?可以切在最左边(等于整根卖出去);可以切在位置1,位置2,。。。

关键的一点是,刀切下去后,左半段就不再切了,继续切右半段。切右半段就变成了一个subproblem。

Naive Recursion:

bubuko.com,布布扣

 

 

Top-down implementation:

bubuko.com,布布扣

Bottom-up implementation: 不容易构想,变量 j 是 subproblem‘s size,从1递增到n,变量 i 用来把每个subproblem 拆分成更小的subproblem,而根据我们这种计算的顺序,当计算 size = j 的时候,< j 的 subproblem 已经计算完毕了。

bubuko.com,布布扣

[DP] Rod-cutting problem,布布扣,bubuko.com

[DP] Rod-cutting problem

原文:http://www.cnblogs.com/Antech/p/3779721.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!