※ 引述《chrisdar (克里斯)》之銘言： : 現今有一池塘長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 我求的Yo[45] 60 78 130 151 155 224 231 238 246 260 352 356 394 397 401 404 409 432 440 445 448 453 460 464 477 484 487 510 517 519 538 554 570 586 602 618 634 649 664 679 694 709 719 723 725 總移動距離為1481不知道有沒有錯 : 我想問還有沒有其他的演算法或想法能支援這個問題，如果化成動態規畫呢？ : 我對於動態規畫的模型僅只於背包問題 XD 謝謝各位。 : 可不可以這樣想 : 假定存在 : 只能移動一格就來完成任務，那麼這時候要怎麼移動才會重疊量最小， : 只能移動兩格就來完成任務，那麼這時候要怎麼移動才會重疊量最小， : ... : 只能移動1500格就來完成任務，那麼這時候要怎麼移動才會重疊量最小， : 那麼問題就回到 如何在有限的移動額度上化解最多的重疊衝突? : ※ 編輯: chrisdar 來自: 123.195.68.196 (11/06 07:44) : ※ 編輯: chrisdar 來自: 123.195.68.196 (11/06 07:48) --

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