现今有一池塘长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 谢谢各位。 -- 可不可以这样想 假定存在 只能移动一格就来完成任务，那麽这时候要怎麽移动才会重叠量最小， 只能移动两格就来完成任务，那麽这时候要怎麽移动才会重叠量最小， ... 只能移动1500格就来完成任务，那麽这时候要怎麽移动才会重叠量最小， 那麽问题就回到 如何在有限的移动额度上化解最多的重叠冲突? ※ 编辑: chrisdar 来自: 123.195.68.196 (11/06 07:45) ※ 编辑: chrisdar 来自: 123.195.68.196 (11/06 07:48) 我把资料又重新排序了 用木头的中点来排序 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)