清华大学出版社 货物储运问题 PRESS 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆,所需的运输费用与新的一堆中集 装箱数成正比。给定各堆的集装箱数,试制定一个运输方案, 使总运输费用最少。 设合并a,1≤jn,所需的最少费用为m[j,则原问题的最 优值为m[1,n]。由最优子结构性质可知, m小=1mnmk-1+m八+叫}1< t=l 根据递归式,按通常方法可设计计算m(i〕)的O(η3)动态规划算法10 货物储运问题 在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运 公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的 2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集 装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案， 使总运输费用最少。 设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最 优值为m[1，n]。由最优子结构性质可知， i j i j m i k m k j a t m i j j t i i k j  =     − + + = =   min { [ , 1] [ , ] [ ]} 0 [ , ] 根据递归式，按通常方法可设计计算m(i,j)的O(n3 )动态规划算法