k****t 发帖数: 184 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: y13706808 (木鱼), 信区: JobHunting
标 题: 请教一个切割木材的问题
发信站: BBS 未名空间站 (Sun Nov 16 00:57:11 2014, 美东)
大家好!我在帖子http://www.mitbbs.com/article_t/JobHunting/32288151.html看到了一个问题,但是楼主没有给出解答,我自己想了半天也不确定,请教哈大家!
有一个长为L的木料需要割开,割的位置在一个数组里A[1...N],从一个地方切开的
cost是当前所切木料的长度,按不同的顺序切割,得到的total cost是不一样的,问怎
么切cost最小。
谢谢大家了! | r*******d 发帖数: 663 | 2 哈,这还用想,肯定是居中切啊。
也就是从最靠近中间点的割的位置切。以后再切就只有接近一半的cost了。
【在 k****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: y13706808 (木鱼), 信区: JobHunting : 标 题: 请教一个切割木材的问题 : 发信站: BBS 未名空间站 (Sun Nov 16 00:57:11 2014, 美东) : 大家好!我在帖子http://www.mitbbs.com/article_t/JobHunting/32288151.html看到了一个问题,但是楼主没有给出解答,我自己想了半天也不确定,请教哈大家! : 有一个长为L的木料需要割开,割的位置在一个数组里A[1...N],从一个地方切开的 : cost是当前所切木料的长度,按不同的顺序切割,得到的total cost是不一样的,问怎 : 么切cost最小。 : 谢谢大家了!
| D******r 发帖数: 5237 | | u****q 发帖数: 24345 | | f****d 发帖数: 3217 | | f****d 发帖数: 612 | 6 觉得就是用DP来做,产生一个NxN matrix,N个columns每个是cut的位置,a[i], 0<=i<
N.
每行的序列号j是第j次cut,1<=j<=N,每个element的值是cut在所在位置最小cost
第一行的值都是L
第二行的值根据第一行和cut第2刀的相应位置找最小
以此类推,第k行的值取决于第k-1的值和cut的位置找最小
直到cut到第N次。答案就出来了。最佳方案当然取决于a[i].
【在 k****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: y13706808 (木鱼), 信区: JobHunting : 标 题: 请教一个切割木材的问题 : 发信站: BBS 未名空间站 (Sun Nov 16 00:57:11 2014, 美东) : 大家好!我在帖子http://www.mitbbs.com/article_t/JobHunting/32288151.html看到了一个问题,但是楼主没有给出解答,我自己想了半天也不确定,请教哈大家! : 有一个长为L的木料需要割开,割的位置在一个数组里A[1...N],从一个地方切开的 : cost是当前所切木料的长度,按不同的顺序切割,得到的total cost是不一样的,问怎 : 么切cost最小。 : 谢谢大家了!
|
|