※ 引述《chrisdar (克里斯)》之銘言： : ※ [本文轉錄自 C_and_CPP 看板] : 作者: chrisdar (克里斯) 看板: C_and_CPP : 標題: [問題] 如何解 池塘邊的木頭 問題 : 時間: Wed Nov 5 21:42:59 2008 : 現今有一池塘長730米寬與木材同寬，池塘邊有45根長短不一的等寬木頭高為H， : 這些等寬木頭一開始的位置為Yi，由於寬度問題容不下兩根木頭同時處在重疊的 : 區間內，還有由一開始的位置搬到合適的地方推下去需要耗費人力，所以希望不 : 要搬離開原始的位置太遠(距離越小越好)，想要請問這些木頭需要搬到哪個位置 : 才能剛剛好推到池塘內而不互相重疊且搬動的距離越小越好。 : 抱歉礙於BBS版面我把座標軸轉了方向： ↑X : 0 → Y 730 : ┌────────────────────────────┐ : │　　　　　　　　　　　　　　　　　　　　　　　　　　　　│池塘 : └────────────────────────────┘ : 　　　　　　┌───────┐ : 　　　　　　└───────┘…………… : Yi[i] H[i] : Yi[45]={60,78,130,151,155,224,236,238,246,260,352,356,394,409,419,429,430,432, : 440,446,452,453,464,464,480,517,523,547,634,709,712,712,712,712,712,712,713, : 713,713,713,713,718,724,725,725} : H[45]={13,4,10,4,4,7,7,5,3,4,3,5,2,4,3,5,23,6,3,3,5,2,4,2,7,3,23,7,2,19,16, : 16,16,16,16,16,15,15,15,15,15,10,4,2,2} : 我的想法：暴力法：使用線性規劃軟體 令 Yo[i] 為新的位置 : 限制式 : 0 <= Yo[0] : Yo[i] + H[i] <= Yo[i+1] i = 0~43 : Yo[44] + H[44] <= 730 : 目標函數 : min = abs(Yo[i]-Yi[i]) i = 0~44 : 可以解到下列這些值 : Yo[45]={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} : 這時候的總移動距離為 1500 : 我想問還有沒有其他的演算法或想法能支援這個問題，如果化成動態規畫呢？ : 我對於動態規畫的模型僅只於背包問題 XD 謝謝各位。 先假定所有取值都取整數 那麼開一個 h 長度(730+1) * n 木材數量(45) 的陣列 DP 可以算出從 h 處, 擺放最後 n 根木材的最少移動量 最簡單先填 n=1, h=730~0 然後再填入 n=2, h=730~0 ... (會用到 n=1 的部份) 以此類推把表格填完 其實不用填 h=730~0 這麼多 因為第 i 根木材的合理位置是有範圍的 在前 i-1 根長度累加的距離之後 在從 i 開始到最後一根的長度累加之前 表填完會求出一個精度在整數的最佳解 如果把格子切細, 比如說 0.1 一格 DP table 就變成 7310 * 45 就是精度在 0.1 的最佳解 這樣算出來的值又會更接進 minimal 不知道這個想法有沒有問題 -- 有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。 　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你 　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也 　是比較不容易被擊倒的人。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.54