Re)8(,） 得一维资源分配问题 maxz=R()+…+Rn(zn) S.l.31+…+2n=Z 2j≥0，j=1,…,n §5.2背包问题 有一个人带一个背包上山，起可携带的物品重量最多α公斤。设有n种物品可供选择装入背包中。 己知代第i种物品每件重量为"，公斤，若携带x件，则上山过程中的作用（价值）为℃x)。问此人应如何 选择携带的物品（即各几件），使所起作用（总价值）最大？这就是著名的背包问题。 与背包问题类似的问题有很多，例如工厂中的下料问题，运输中的货物装载问题，人造卫星内的物 品装载问题。 静态问题： maxz=C(x)+…+cn(xn) s.1.11+…+nxn≤a x,≥0，intj=1,…,n 动态规划：设 阶段：把背包内装入一种物品作为一个阶段，k=L,…,: 状态变量s:用于装第k种物品至第n种产品的总重量，0≤s≤a; 决策变量4：装第k种物品的数量（即u,=x),允许决策集：0≤w山，≤s,山：it,即 U(s)={4=0,l, 状态转移方程：Sk+1=Sx一州4； 指标函数：，4)=c4),,4,,4=e)(加武) 最优值函数f(S):当背包中可装入第k种物品至第n种物品的总重量为S,时可获得的最大价值。 则得基本方程： (Sx)=max fcr(ux)+(sx-wxug)),k =n,...,1 fn+(Sn+)=0 最终求得(a)即为最大价值。 二维背包问题：两种限制 静态规划： maxz=C(x)+…+cn(xn) s.t.9x1+…+1wnxn≤a x+…+vnxn≤b x,≥0，int,j=l,…,n 动态规划： 55 0 / ( ) max ( , ) i i i i ii k i y zb z by R z g y ≤ ≤ a − = 得一维资源分配问题 1 1 1 max ( ) ( ) . . 0, 1, , n n n j z Rz Rz st z z Z zj n = ++ ++= ≥ = " " " §5.2 背包问题 有一个人带一个背包上山，起可携带的物品重量最多 a 公斤。设有 n 种物品可供选择装入背包中。 已知代第 i 种物品每件重量为 wi 公斤，若携带 xi件，则上山过程中的作用(价值)为 ci(xi)。问此人应如何 选择携带的物品(即各几件)，使所起作用(总价值)最大？这就是著名的背包问题。 与背包问题类似的问题有很多，例如工厂中的下料问题，运输中的货物装载问题，人造卫星内的物 品装载问题。 静态问题： 1 1 1 1 max ( ) ( ) . . 0,int, 1, , n n n n j z cx cx st wx w x a x j n = ++ ++ ≤ ≥ = " " " 动态规划：设 阶段：把背包内装入一种物品作为一个阶段， k n =1, , " ； 状态变量 k s ：用于装第 k 种物品至第 n 种产品的总重量，0 k ≤ s ≤ a ； 决策变量 k u ：装第 k 种物品的数量(即 k k u x = )，允许决策集：0 ≤ wu s kk k ≤ ， k u :int，即 ( ) { | 0,1, , } k kk k k k s Us uu w ⎡ ⎤ = = ⎢ ⎥ ⎣ ⎦ " ； 状态转移方程： k k kk 1 s s wu + = − ； 指标函数： (, ) () kk k k k vsu cu = ， , 1 (, , ,, , ) () n kn k k n n n j j j k V su sus cu + = " = ∑ （加式） 最优值函数 ( ) k k f s ：当背包中可装入第 k 种物品至第 n 种物品的总重量为 k s 时可获得的最大价值。 则得基本方程： 1 0,1, , 1 1 ( ) max { ( ) ( )}, , ,1 ( )0 k k k k k k k k k kk s u w n n f s c u f s wu k n f s + ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ + + ⎧ = +− = ⎪ ⎨ ⎪ ⎩ = " " 最终求得 1f ( ) a 即为最大价值。 二维背包问题：两种限制 静态规划： 1 1 1 1 1 1 max ( ) ( ) . . 0,int, 1, , n n n n n n j z cx cx st wx w x a vx vx b x j n = + + ++ ≤ ++ ≤ ≥ = " " " " 动态规划：