第五章动态规划`分析.ppt

第五章 动态规划Dynamic Programming 第一节 多阶段决策过程及实例 Multiperiod Decision Process and example 第二节 逆序递推法Backward Recursion 第三节 动态规划的基本原理和基本概念 第四节 动态规划在多阶段决策中的应用DP Application in Multiperiod Decision 4.4 背包问题 第五节?? 多维变量问题 s1= 0，s2= 0,1,2,3 K = 1，求f1(s2) ： f1(0) = R1(1) = 4(千元)， f1(1) = R1(2) = 5， f1(2) = R1(2) = 4+2= 6， f1(3) = R1(3) = 4+3 = 7 s3= 0,1,2,3 K = 2，求f2(s3) ： s3= 0 R2(0)+f1(2) = 0+6； R2(1)+f1(1) = 4+5=9； R2(2)+f1(0) = 4+4=8 s3= 1 R2(0)+f1(3) = 0+7+1=8 =f2(1) ； R2(1)+f1(2) = 4+6+1=11； R2(2)+f1(1) = 4+5+1=10； R2(3)+f1(0) = 4+4+1=9 s3= 2 R2(1)+f1(3) = 4+7+2=13； R2(2)+f1(2) = 4+6+2=12； R2(3)+f1(1) = 4+5+2=11； R2(4)+f1(0) = 4+4+2=10 s3= 3 R2(2)+f1(3) = 4+7+3=14； R2(3)+f1(2) = 4+6+3=13； R2(4)+f1(1) = 4+5+3=12 K=3, s4 = 0,1,2 ； 2≤ x3 ≤4 s4 = 0 R3(2)+f2(3) = 4+12=16； R3(3)+f2(2) = 4+10=14； R3(4)+f2(1) = 4+8=12= f3(0) s4 =1 R3(3)+f2(3) = 4+12+1=17； R3(4)+f2(2) = 4+10+1=15 s4 =2 R3(4)+f2(3) = 4+12+2=18 K=4, s5 = 0,1,2,3 ； 1≤ x4≤4 s5 = 0 R4(1)+f3(2) = 4+18=22； R4(2)+f3(1) = 4+15=19； R4(3)+f3(0) = 4+12=16= f4(0) s5 = 1 R4(2)+f3(2) = 4+18+1=23； R4(3)+f3(1) = 4+15+1=20； R4(4)+f3(0) = 4+12+1=17 s5 = 2 R4(3)+f3(2) = 4+18+2=20； R4(4)+f3(1) = 4+15+2=21 s5 = 3 R4(4)+f3(2) = 4+18+3=25 K=5 , s6 = 0,1 ； x5 ≤3 s6= 0 R5(0)+f4(2) = 0+21=21； R5(1)+f4(1) = 4+17=21； R5(2)+f4(0) = 4+16=20 s6= 1 R5(0)+f4(3) = 0+24+1=25； R5(1)+f4(2) = 4+21+1=26； R5(2)+f4(1) = 4+17+1=22； R5(3)+f4(0) = 4+16+1=21 = f5(1) K=6 , s7 = 0 ； x6≤1 R6(0)+f5(1) = 0+21=21= f6(0) ； R6(1)+f5(1) = 4+20=24 月份 1 2 3 4 5 6 交货量，百件 1 2 5 3 2 1 生产量，百件 4 0 4 3 3 0 有一个人带一个背包上山，可携带物品重量限度为W公斤，设有n种物品可供选择。已知第i种物品重量为wi公斤，上山过程中的作用（价值）是携带数量xi的函数ci(xi)。问应如何选择携带物品，使总的作用最