动态规划-背包问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,动态规划的应用背包问题,下面用动态规划方法来求解：,1.,阶段,k,：即需要装入的,n,种物品的次序,每段装入一种,共,n,段。,2.,状态变量,k,s,：即在第,k,段开始时,允许装入前,k,种物品的总重,量，显然有,n,s,=,b,因,n,s,已知故可采用顺序解法。,3.,决策变量,k,x,：即装入第,k,种物品的件数,4.,状态转移方程：,k,k,k,k,x,a,s,s,-,=,-,1,允许的决策集合是：,=,k,k,k,k,k,k,a,s,x,x,s,D,0,|,),(,且为整数,5.,基本方程是,:,=,=,-,+,=,-,n,k,s,f,x,a,s,f,x,c,s,f,k,k,k,k,k,k,k,k,.,2,1,0,),(,),(,max,),(,0,0,1,实例,一贩运商拟用一,10,吨载重量的大卡车装载,3,种货物,有资料,如下表,问应如何组织装载,可使总价值最大,?,解：,设装载每一种货物的件数为,i,x,，则有：,maxz,=4,1,x,+5,2,x,+6,3,x,s.t,.3,1,x,+4,2,x,+5,3,x,10,0,i,x,且为整数,用动态规划方法的顺序解法求解，则,当,k=1,时,1,3,0,1,1,4,),(,max,1,1,1,1,x,s,f,x,s,x,为整数,=,货物编号,1 2 3,单位重量,（吨）,单位价值,3 4 5,4 5 6,这是一个简单的线性规划问题,0,1,3,x,1,s,即,3,0,1,1,s,x,因线性,规划的最大值只能在极点取得,于是有,),3,(,4,4,max,),(,1,1,3,0,1,1,1,1,s,Int,x,s,f,s,x,=,=,计算结果可列入下表,:,1,s,0 1 2 3 4 5 6 7 8 9 10,1,x,0,0,0 1,1,1 2,2,2 3,3,),(,1,1,s,f,0,0,0 4,4,4 8,8,8 12,12,当,k=2,时，,+,-,=,2,2,2,1,4,0,2,2,5,),4,(,max,),(,1,2,2,x,x,s,f,s,f,s,s,x,计算结果如下表：,S,2,0 1 2 3 4 5 6 7 8 9 10,x,2,0 0 0 0 0 1 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2,V,2,0 0 0 0 0 5 0 5 0 5 0 5 0 5 10 0 5 10 0 5 10,f,1,+V,2,0 0 0 4 4 5 4 5 8 5 8 9 8 9 10 12 9 10 12 13 10,f,2,(s,2,)0 0 0 4 5 5 8 9 10 12 13,x,2,*,0 0 0 0 1 1 0 1 2 0 1,+,-,=,2,2,2,1,4,0,2,2,5,),4,(,max,),(,1,2,2,x,x,s,f,s,f,s,s,x,V,2,5x,2,当,k=3,时,因,3,s,=10,故,2,s,=10-5,3,x,5x,3,s,3,即,x,3,2,，所以,3,f,（,10,）,=,max,2,0,3,x,2,f,(10-5,3,x,)+6,3,x,=,max,2,1,0,3,=,x,2,f,(10-5,3,x,)+6,3,x,=,max,2,f,(10),2,f,(5)+6,2,f,(0)+12,=,max13,5+6,0+12=13,即,*,3,x,=0,依状态转移方程反推,此时有,2,s,=10,当,2,s,=10,时,依第,2,段计,算结果,*,2,x,=1,，当,2,x,=1,，,2,s,=10,时,依,1,s,=,2,s,-,4,2,x,有,1,s,=6,，,由第一段,计算结果知,当,1,s,=6,时,*,1,x,=2.,即最优方案为：,*,1,x,=2,*,2,x,=1,*,3,x,=0,最大,价值为,13,。,