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