PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 如何解池塘邊的木頭問題

看板Prob_Solve (計算數學 Problem Solving)作者ledia (下班後才下棋)時間16年前 (2008/11/06 03:33)推噓7(7推 0噓 2→)

留言9則, 4人參與討論串2/8 (看更多)

※ 引述《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

Re: [問題] 如何解 池塘邊的木頭 問題

Re: [問題] 如何解池塘邊的木頭問題