动态规划-背包问题.ppt

《动态规划-背包问题.ppt》由会员分享，可在线阅读，更多相关《动态规划-背包问题.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 动态规划的应用背包问题动态规划的应用背包问题下面用动态规划方法来求解：1.阶段k：即需要装入的n种物品的次序,每段装入一种,共n段。2.状态变量ks：即在第k段开始时,允许装入前k种物品的总重量，显然有ns=b,因ns已知故可采用顺序解法。3.决策变量kx：即装入第k种物品的件数4.状态转移方程：kkkkxass-=-1允许的决策集合是：=kkkkkkasxxsD0|)(且为整数5.基本方程是:=-+=-nksfxasfxcsfkkkkkkkk,.,2,10)()(max)(001实例 一贩运商拟用一10吨载重量的大卡车装载3种货物,有资料如下表,问应如何组织装载,可使总价值最大?解：设装载

2、每一种货物的件数为ix，则有：maxz=41x+52x+63x s.t.31x+42x+53x10 0ix 且为整数用动态规划方法的顺序解法求解，则 当k=1时,130114)(max1111xsfxsx为整数=货物编号1 2 3单位重量（吨）单位价值3 4 54 5 6这是一个简单的线性规划问题,013x1s即3011sx,因线性规划的最大值只能在极点取得,于是有)3(44max)(11301111sIntxsfsx=计算结果可列入下表:1s0 1 2 3 4 5 6 7 8 9 10 1x0 0 0 1 1 1 2 2 2 3 3)(11sf0 0 0 4 4 4 8 8 8 12 12当

3、k=2时，+-=222140225)4(max)(122xxsfsfssx计算结果如下表：S2 0 1 2 3 4 5 6 7 8 9 10 x2 0 0 0 0 0 1 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2 V2 0 0 0 0 0 5 0 5 0 5 0 5 0 5 10 0 5 10 0 5 10 f1+V2 0 0 0 4 4 5 4 5 8 5 8 9 8 9 10 12 9 10 12 13 10 f2(s2)0 0 0 4 5 5 8 9 10 12 13 x2*0 0 0 0 1 1 0 1 2 0 1+-=222140225)4(max)(122xxsfsfssx V2 5x2当k=3时,因3s=10,故2s=10-53x,5x3s3即x32，所以3f（10）=max203x2f(10-53x)+63x =max2,1,03=x2f(10-53x)+63x =max2f(10),2f(5)+6,2f(0)+12 =max13,5+6,0+12=13即*3x=0,依状态转移方程反推,此时有2s=10,当2s=10时,依第2段计算结果*2x=1，当2x=1，2s=10时,依1s=2s-42x有1s=6，由第一段计算结果知,当1s=6时,*1x=2.即最优方案为：*1x=2,*2x=1,*3x=0,最大价值为13。