动态规划之最短路问题背包问题排序问题.pptVIP

排序 4+3 6+4 5+8 6+5 6+4 8+6 5+3 7+5 3+9 10+3 B + C A+B 复原 3 4 6 8 5 6 4 6 8 3 5 7 9 3 10 C B A 计算 T = 6+10+8+7+6+4+3 = 44 计算依据： 练习： 11 8 5 10 7 9 8 2 7 7 4 6 C B A T=45 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，…，x。上式可变为： 所以，根据动态规划的最优化原理，有下式： 例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资 利润 0 10 20 30 40 50 60 g1(x) 0 20 50 65 80 85 85 g2(x) 0 20 40 50 55 60 65 g3(x) 0 25 60 85 100 110 115 g4(x) 0 25 40 50 60 65 70 解：依据题意，是要求 f4(60) 。 按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) ＝ g1(x)，得到下表 投资 利润 0 10 20 30 40 50 60 f1(x) ＝ g1(x) 0 20 50 65 80 85 85 最优策略 0 10 20 30 40 50 60 第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。 最优策略为（40，20），此时最大利润为120万元。 同理可求得其它 f2(x) 的值。 最优策略为（30，20），此时最大利润为105万元。 最优策略为（20，20），此时最大利润为90万元。 最优策略为（20，10），此时最大利润为70万元。 最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。 f2(0) ＝0。最优策略为（0，0），最大利润为0万元。 得到下表 最优策略为（20，0），此时最大利润为50万元。 投资 利润 0 10 20 30 40 50 60 f2(x) 0 20 50 70 90 105 120 最优策略 (0,0) (10,0) (0,10) (20,0) (20,10) (20,20) (30,20) (40,20) 第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。 最优策略为（20，10，30），最大利润为155万元。 同理可求得其它 f3(x) 的值。得到下表 投资 利润 0 10 20 30 40 50 60 f3(x) 0 25 60 85 110 135 155 最优 策略 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 第四阶段：求 f4(60)。即问题的最优策略。 最优策略为（20，0，30，10），最大利润为160万元。 练习： 求投资分配问题得最优策略，其中a＝50 万元，其余资料如表所示。 投资 利润 0 10 20 30 40 50 g1(x) 0 21 40 52 80 85 g2(x) 0 15 36 50 73 100 g3(x) 0 25 60 65 68 70 例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。 地区 销售点 0 1 2 3 4 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 x1=2，x2=1，x3=1，f3(4)=47 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品 1 2 … j … n 重量（公斤/件） a1 a2 … aj … an 每件使用价值 c1 c2 … cj … cn 这就是背包问题。类似的还有工厂里的下料问题