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