作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 如何解 池塘边的木头 问题
时间Fri Nov 7 19:28:36 2008
1F：推 chrisdar:我先去搜寻相关资料 谢谢 关键字应该是 状态空间树 吧 11/07 18:15
2F：→ DJWS:恩...我讲的是动态规划法 XD 11/07 18:24
3F：→ DJWS:不过我没有实际写出来 所以不敢保证我的想法对不对 11/07 18:25
4F：推 Fenikso:排序後不一定能找到最佳解 11/07 18:32
现在有两根木头，其左端位置分别为 x1 和 x2。
令 x1 <= x2。
这两根木头被人力推动後，木头左端的相对位置只有两种情形：
甲、一左一右：交由动态规划解决。
乙、一右一左：如果这两根木头都会推到水里，那麽这就是浪费力气的推法。比甲还差。
故排序是可行的，
除非有些木头不打算推到水里。
－
补充一下。
上一篇所说的方法是假设有些木头不必放到水里。
木头不必都放入水里的话，
就我的认知，这样要用动态规划解决，仍需指数时间。
如果全部的木头都要放入水里，
那麽状态空间设定成: (池塘宽度,木材数目) 就可以了。
就跟ledia板友所描述的是一样的。
这样的问题用动态规划应可在多项式时间求得。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.137.83.198
5F：推 chrisdar:PS.木头一定要推到水里(数学上=彼此区间不重叠) 11/07 19:43
※ 编辑: DJWS 来自: 220.137.83.198 (11/07 20:04)