第21讲_动态规划(投资分配问题)

1、ACM-ICPC培训培训投资分配问题ACM算法设计与分析王建芳ACM-ICPC培训培训投资分配问题河南理工大学ACM-ICPC培训 现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为最大。 nixaxxgziniiniii.2.1 0)( max11据此，有下式：河南理工大学ACM-ICPC培训 令：fk(x) 表示以数量为x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问题。 当

2、 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1kn 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0y x ），此时还剩 x y（万元）的资金需要分配给前 k1 个工厂,如果采取最优策略，则得到的最大利润为fk1(xy) ,因此总的利润为： gk(y) fk1(xy) 投资分配问题 nixaxxgziniiniii.2.1 0)( max11河南理工大学ACM-ICPC培训 nkyxfygxfkkxyk.)()(max)(3210 其中 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，x。上式可变为： )()(max)(,yxfygx

3、fkkxyk 1210所以，根据动态规划的最优化原理，有下式：投资分配问题河南理工大学ACM-ICPC培训设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资投资利润利润0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570依据题意，是要求 f4(60) 。投资分配问题河南理工大学ACM-ICPC培训按顺序解法计算。第一阶段：求 f1(x)。显然有 f1(x) g1(x)，得到下表 投资投资利润利润01020

4、30405060f1(x) g1(x)0205065808585最优策略最优策略0102030405060第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60(1260,10,02yfygfy 投资分配问题河南理工大学ACM-ICPC培训12006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最优策略为（40，20），此时最大利润为120万元。同理可求得其

5、它 f2(x) 的值。 )60()(max)60(1260,10,02yfygfy 投资分配问题河南理工大学ACM-ICPC培训2210 ,10 ,50212121212121(50)m ax()(50) (0)(50)(10)(40)(20)(30) 105(30)(20)(40)(10)(50)(0)yfgyfygfgfgfgfgfgf最优策略为（最优策略为（3030，2020），此时最大利润为），此时最大利润为105105万元。万元。投资分配问题河南理工大学ACM-ICPC培训2210 ,10 ,40(40)m ax()(40)90yfgyfy最优策略为（20，20），此时最大利润为90

6、万元。2210 ,10 ,20 ,30(30)m ax()(30)70yfgyfy最优策略为（20，10），此时最大利润为70万元。投资分配问题河南理工大学ACM-ICPC培训2210,10,20(20)m ax()(20) 50yfgyfy2210 ,10 ,(10)m ax()(10)20yfgyfy最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。 f2(0) 0。最优策略为（0，0），最大利润为0万元。 得到下表最优策略为（20，0），此时最大利润为50万元。投资分配问题河南理工大学ACM-ICPC培训 投资投资利润利润0102030405060f2(x)0205

7、07090105120最优策略最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60(2360,10,03yfygfy 投资分配问题河南理工大学ACM-ICPC培训1550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323 fgfgfgfgfgfgfg最优策略为（

8、最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表投资分配问题河南理工大学ACM-ICPC培训 投资投资利润利润0102030405060f3(x)0256085110135155最优最优策略策略(0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第四阶段：求 f4(60)。即问题的最优策略。)60()(max)60(3460,10,04yfygfy投资分配问题河南理工大学ACM-ICPC培训16007025656060855011040135251550max)0()60()10()50