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

看板Programming作者chrisdar (克里斯)時間17年前 (2008/11/05 21:44)推噓7(7推 0噓 12→)

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

現今有一池塘長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 謝謝各位。 --

推

WalkingIce

11/06 00:53, , 1^F

11/06 00:53, 1^F

可不可以這樣想假定存在只能移動一格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，只能移動兩格就來完成任務，那麼這時候要怎麼移動才會重疊量最小， ... 只能移動1500格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，那麼問題就回到如何在有限的移動額度上化解最多的重疊衝突? ※ 編輯: chrisdar 來自: 123.195.68.196 (11/06 07:45) ※ 編輯: chrisdar 來自: 123.195.68.196 (11/06 07:48)

推

bobju

11/06 08:12, , 2^F

11/06 08:12, 2^F

→

bobju

11/06 10:16, , 3^F

11/06 10:16, 3^F

→

bobju

11/06 10:16, , 4^F

11/06 10:16, 4^F

→

chrisdar

11/06 10:54, , 5^F

11/06 10:54, 5^F

→

Lordaeron

11/06 11:29, , 6^F

11/06 11:29, 6^F

推

bobju

11/06 12:47, , 7^F

11/06 12:47, 7^F

→

chrisdar

11/06 18:44, , 8^F

11/06 18:44, 8^F

→

chrisdar

11/06 18:45, , 9^F

11/06 18:45, 9^F

推

bobju

11/06 21:53, , 10^F

11/06 21:53, 10^F

→

bobju

11/06 21:54, , 11^F

11/06 21:54, 11^F

→

bobju

11/06 21:55, , 12^F

11/06 21:55, 12^F

→

bobju

11/06 21:56, , 13^F

11/06 21:56, 13^F

推

bobju

11/07 09:06, , 14^F

11/07 09:06, 14^F

→

bobju

11/07 09:06, , 15^F

11/07 09:06, 15^F

我把資料又重新排序了用木頭的中點來排序 Yi[45] = { 60, 78,130,151,155,224,236,238,246,260,352,356,394,409,419, 429,432,430,440,446,453,452,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, 6, 23, 3, 3, 2, 5, 2, 4, 7, 3, 23, 7, 2, 19, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 10, 4, 2, 2 } Solution: 1492 Yo[45] = { 60, 78,130,151,155,224,234,241,246,260,352,356,394,409,413, 416,421,427,450,453,456,458,464,466,480,487,490,513,520,522, 541,557,573,589,605,621,637,652,667,682,697,712,722,726,728 } 同樣的模型不一樣的順序值變小了 ( 在其他板上獲得的資訊 ) ※ 編輯: chrisdar 來自: 123.195.68.196 (11/07 12:42)

推

bobju

11/07 22:06, , 16^F

11/07 22:06, 16^F

→

bobju

11/07 22:06, , 17^F

11/07 22:06, 17^F

→

chrisdar

11/07 22:23, , 18^F

11/07 22:23, 18^F