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 的大作中提到】
: 【 以下文字转载自 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 的大作中提到】
: 【 以下文字转载自 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最小。
: 谢谢大家了！
|
|
