我跑出来的结果也是第一组(原始资料) 1500, 第二组(中点排序) 1492, 不过结果序列跟前文当中公布的不太一样. Solution: cost=1500: 60,78,130,151,155,224,234,241,246,260, 352,356,394,405,409,412,417,440,446,449, 452,457,464,468,480,487,490,513,520,522, 541,557,573,589,605,621,637,652,667,682, 697,712,722,726,728 Solution: cost=1492: 60,78,130,151,155,224,234,241,246,260, 352,356,394,409,414,417,422,428,451,454, 457,459,464,466,480,487,490,513,520,522, 541,557,573,589,605,621,637,652,667,682, 697,712,722,726,728 其实cost相同, 但结果序列不同是可以预期的, 因为相同cost的结果序列不只 一组而已. 另外, 为什麽排序过的资料跟原始资料的条件相同(位置,长度皆相同), 只是 排列顺序不同就产生不同的结果呢? 我猜可能是我们用的演算法是为了简化问 题的复杂度, 只针对特殊情况求一个大致还可以接受的解, 并没有真正把所有 的情况都考虑进去. 对於如何解这个问题我是这样想的: 对於每一个木块, 都存在一个偏移值, 使得所有的木块可以两两不相重叠. 这个偏移值呢, 是个整数, 其正负随着木块往左移或往右移而定, 若木块不移 动, 则偏移值为0. 如此可以想出, 若将每一个木块的偏移值依序排开, 应该会是以下这样: (D0, D1, D2, ........, D44) , -Zl <= Dn <= Zr , Zl,Zr是整数,其范围取 决於题目设定的条件: 相邻的木块不得重叠(可以相接), 边界木块不能跨出河 边. 由於我们无法预知究竟哪种结果序列可以让所有木块可以两两不相重叠, 在没 有公式解之前, 大概是以列举的方式来思考: 所有情况等於从D0所有可能情况 一路乘到D44的所有可能情况, 可以想像得到这范围肯定是个天文数字. 要把所有结果序列列举出来的演算法很容易写, 就是一个递回呼叫函式做深先 搜寻. 以D0为第0层, D1为第1层...逐层传递下去(再回传). 再利用一个回圈, 从 Zl ~ Zr 的范围内, 跑递回函式把所有情况通通跑完. 演算法像这样: triversal(i) { // your code for ( Zl[i] to Zr[i] ) { triversal (i+1) } // your code } 这跑完大概不知是多久以後了, 当然我们也不是要列举所有情况, 只是在这 个想法的基础上, 接着引入动态规划的概念, 计算移动每块木块的最小成本. 并且将计算出来的值, 贡献给後续的运算, 以空间换取时间, 大幅降低上述 演算法的时间复杂度. (休息一下, 想接着该如何写..) 接着, 这里先提出一个假设, 假设这些木块全部都以'以最左边的木块为准, 向左看齐!'的方式来调整彼此的间距, 使得两两不互相重叠, 这样的规则下 去演算, 可以求得最小成本解. 这个假设只是用来方便我们跑程式, 看看跑 出来的解跟运用其它方式跑出来的解互相验证是否能够一致. 接着我们再看: 在以上述规则来调整木块位置的情况下, 为木块做编号. 因 为'向左看齐'的关系, 所以定义木块的左端为头, 右端为尾, 我们描述一 个木块的位置是以头的位置为准. 最左边的木块为0号, 接着次左的为1号, 再次左的为2号, 由左往右逐次编号, 若有两块以上的木块头是在同一个位 置, 则随意编号, 唯一旦编号确定後则不得再改变, 最後一个木块则为44号. 关於木块的起始位置以及长度值, 就各别以两个阵列来存放, 以木块编号为 索引值. 接下来, 引进'最小成本'的观念. 在跑程式的过程当中, 只要不与相邻的木 块重叠, 木块是有可以被移动的, 而且可能有很多个位置可以任凭挑选. 当 它被移动时, 产生一个成本: 这个成本是这麽计算的: 木块[i][位置].成本 = abs(木块[i].位置 - 木块[i].起始位置) 我们从木块[0]开始, 由左向右依序执行移动位置的动作. 轮到木块[i], 木 块[i]可动也可不动, 移不移动的依据, 就是不能与其左邻的木块重叠, 若是 重叠到, 则必须向右移位, 使其不与左邻木块重叠. 木块[i]定位後, 接着才 能轮到木块[i+1]. 在这个规则下, '挤'出了一个可以用来计算最小成本的重要依据. 也就是对於 一个已经确定位置的木块[i]而言, 其後的木块[i+1]到木块[44]不管怎麽移动 , 它们所产生的成本总和必然为有限, 而且这麽多组成本总和中, 必定存在一 个最小值. 所以对於任意一个木块[i]而言, 在它所有的可能被安置的位置上, 必然可以 计算出一个'最小成本值'. 木块[i][位置].最小成本值 = 木块[i][位置].成本 + min(总成本1(木块[i+1]..木块[44]),总2,..,总n) 木块[i][位置].最小成本值必定是一个定值, 不可能变动. 所以当我们以递 回深先拜访的方式, 从左到右扫过每一个木块时, 每一个木块在其可能被移 动到的位置上, 都能够经由递回函式的返回所回传的最小总成本值, 加上其 本身的成本值而计算出其在该位置上的最小成本值. 这个最小成本值用一个 资料结构记起来, 当稍後在递回函式的游回历程中这个木块在这个位置又被 重复拜访到(会被重复拜访到好几遍)的时候, 其最小成本值只需第一次计算 到, 以後皆可重复使用, 不需再经递回历程计算.. 如此可以有效降低递回 函式游回的时间复杂度. (再休息一下, 剩最後一个阶段) 当计算每一个木块在某个位置时所产生的最小成本的方式确定後, 接着就是 将递回函式的主体写出来, 以及一些处理细节的小程序. 它的主要功能是把 "(木块编号,位置,最小成本)关联表"建立起来, 以供後段应用. 当"(木块编号, 位置, 最小成本)关联表"建立起来以後, 只要 观察木块[0]的所有位置所各自对应的最小成本, 再从中取最小值, 就是题 目所要的答案了. 至於展开所有木块的位置所形成的结果序列, 也是从这个 关联表下去演算. 能够符合最小成本的结果序列应该还蛮多组的, 有空有需 要的话再捞看看. 後述: 上述解这个问题所采用的演算法, 未必能够保证得到的就是最小成本解. 除 了必要的数学证明需要更深厚的功底外, 还有两个原因是: 一, 我只采用 '向左看齐'去跑(而且还锁定第0个木块不移动, 这做了太多限制了), 没有采 用'向右看齐'去跑, 谁能证明这两种方式等价呢? 而且又该如何证明其必然 包含木块的所有移动的情况呢? 二, 同样的一堆木块, 因为运算顺序不同而 导致算出来的结果不同, 这在实务上大概也无法让人觉得信服. 所以说, 革 命尚未成功, 同志仍需努力. 相信应该有更完整的solution, 不过我大概已 经没有战力再继续try下去了. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 211.74.253.114 ※ 编辑: bobju 来自: 211.74.253.114 (11/08 02:27) ※ 编辑: bobju 来自: 211.74.253.114 (11/08 02:29) ※ 编辑: bobju 来自: 211.74.253.114 (11/08 07:26) ※ 编辑: bobju 来自: 211.74.253.114 (11/08 08:07)