§3背包间题 有 个人背包上山，其可携带物品重量限度为a公厅。设有n种 物品可供他选择装入背包中，己知第种物品每件重为w公斤，在 上山过程中的作用是数量x的函数c(x)。间此人应如何选择携带 物品（各几件），使所起作用最大。这就是著名的背包间题。类似 的同题有运输中的货物装载数量、人造卫星内的物品装载间题等 设x为第种物品的装入数量，则问题的数学模型为： max Z=>c(x 含a ,≥0且尚营款，=1,2，e 这是一个整数规划问题。 如果x只取0或1，又称0-1背包问题 这类问题可以用动态规划方法求解。 按可装入背包的物品的类别分阶段：k=1,2,.,n 犬态变量x表示允许装入的第k种物品至第n种物品的总重量： 快策变量u表示装入的第k种物品的件数，则状态转移方程为： k+1-Xk Uk Wk 设人(x,)为装入第k种物品到第种物品所对应的最大使用价 值。则动态规划基本方程是：
§3 背包问题 有一个人背包上山，其可携带物品重量限度为a公斤。设有n种 物品可供他选择装入背包中，已知第i种物品每件重为wi公斤，在 上山过程中的作用是数量xi的函数ci (xi )。问此人应如何选择携带 物品（各几件），使所起作用最大。这就是著名的背包问题。类似 的问题有运输中的货物装载数量、人造卫星内的物品装载问题等。 设xi为第i种物品的装入数量，则问题的数学模型为： = ( ) = n i Z ci xi 1 max wx a n i i i =1 Xi≥0且为整数，i=1,2, …,n 这是一个整数规划问题。如果xi只取0或1，又称0-1背包问题。 这类问题可以用动态规划方法求解。 按可装入背包的物品的类别分阶段：k=1，2，…，n. 状态变量xk表示允许装入的第k种物品至第n 种物品的总重量； 决策变量uk表示装入的第k种物品的件数，则状态转移方程为： xk+1=xk-uk wk. 设fk（xk）为装入第k种物品到第n种物品所对应的最大使用价 值。则动态规划基本方程是：
fk (xk)=max {ck (uk)+fk+(xk+1)) ft1(xt1)=0k=n,n-1,…,1 然后， 由后至前逐步计算出f(xn),fn1(x） 及相应的u（X),h1(X-1) u1(X),最后算得f(x) 就是所求的最大价值，再按计算顺序反推回去，即可得到最优 方案。 例5（载货问题）今有一辆载重量为10吨的卡车，有四种 需要运输的货物，均可用此车装运。若已知这四种货物每一种 的重量和价值如下表所示。在载重量许可的条件下，试确定使 每车装载货物价值最大的载货方案。 货物代号 1 2 3 重量 (吨/件) 2 3 4 5 价值（千元件） 3 5 6 解：以分别装载各种货物的顺序为阶段k=1,2,3,4; 选取k阶段至4阶段允许装载的重量x为状态变量；决策变量u 表示第k种货物装载的件数，则状态转移方程为： Xk+1-Xk Uk Wk
fk（xk）= max｛ck（uk）+fk+1（xk+1）｝ uk fn+1（xn+1）=0 k=n,n-1, …,1 然后，由后至前逐步计算出fn（xn）， fn-1（xn-1），…，f1（x1） 及相应的un（xn）, un-1（xn-1），…，u1（x1）,最后算得f1（x1） 就是所求的最大价值，再按计算顺序反推回去，即可得到最优 方案。 例5（载货问题）今有一辆载重量为10吨的卡车，有四种 需要运输的货物，均可用此车装运。若已知这四种货物每一种 的重量和价值如下表所示。在载重量许可的条件下，试确定使 每车装载货物价值最大的载货方案。 货物代号 1 2 3 4 重量（吨/件） 2 3 4 5 价值（千元/件） 3 4 5 6 解：以分别装载各种货物的顺序为阶段k =1，2，3，4； 选取k阶段至4阶段允许装载的重量xk为状态变量；决策变量uk 表示第k种货物装载的件数，则状态转移方程为：xk+1=xk-uk wk
设(xk)为装入第k种至第4种货物的最大总价值。于是： k=4x=0,1,…,10(吨)，注意：第4种货物重为5（吨/件） 价值是6（千元/件） 0, x4=0,1,2,3,4,u4(X)=0 X45, u4(X4 12,X4=10, u4（X)=2 k=3X3=0,1,,10(吨)，重4（吨/件），价值5 (千元/件) 5（X3)=0,x3=0,1,2,3, U3 （X3)=0 (4)=max{5+f(0),0+f1 (4) =max{5+0,0+0}=5, (4)=1 (5)=max {5+f(1),0+f (5) =max{5+0,0+6}=6, Uk (5)=0 (6)=max {5+f1(2),0+f (6)} -max {5+0,0+6}=6, U (6)=0 (7) =max {5+f(3),0+(7)) max {5+0,0+6}=6, u3(7)=0 (8) -max {10+f(0),5+f(4),0+f斤(8)} =max{10+0,5+0,0+6}=10, u3(8)=2
设fk（xk）为装入第k种至第4种货物的最大总价值。于是： k=4 x4=0,1, …,10（吨），注意：第4种货物重为5（吨/件）， 价值是6 （千元/件） 0， x4=0，1，2，3，4， u4（ x4）=0 f4（x4）= 6， x4=5，6，7，8，9， u4（ x4）=1 12， x4=10， u4（ x4）=2 k=3 x3=0,1, …,10（吨），重4（吨/件），价值5 （千元/件） f3（ x3）=0，x3=0，1，2，3， u3（x3）=0 f3（4）=max｛5+f4（0）,0+f4（4）｝ =max｛5+0,0+0｝=5, u3（4）=1 f3（5）=max｛5+f4（1）,0+f4（5）｝ =max｛5+0,0+6｝=6, u3（5）=0 f3（6）=max｛5+f4（2）,0+f4（6）｝ =max｛5+0,0+6｝=6, u3（6）=0 f3（7）=max｛5+f4（3）,0+f4（7）｝ =max｛5+0,0+6｝=6, u3（7）=0 f3（8）=max｛10+f4（0）,5+f4（4）,0+f4（8）｝ =max｛10+0,5+0,0+6｝=10, u3（8）=2
(9) =max (10+f(1),5+f(5),0+f(9) max {10+0,5+6,0+6}=11, u3(9)=1 5(10) -max (10+f(2),5+f(6),0+f(10)) -max {10+0,5+6,0+12}=12 u3(10)=0 k=22=0,2,4,6,8,10(吨) 注意： 第2种货物重为3（吨/件），价值是4（千元/件）》 第1种货物重为2（吨/件），价值是3（千元/件） 5(0)=(2)=0, 山2(0)u2(2)=0 (4) =max{4+f5(1),0+5(4)}=max{4+0,0+5}=5 42(4)=0 (6) =max {8+5(0),4+5(3),0+6(6) max {8+0,4+0,0+6}=8, 山2(6)=2 (8) =max {8+5(2),4+5(5),0+5(8)) max {8+0,4+6,0+10}=10, u2(8)=0 (10) -max {12+6(1),8+6(4),4+5(7),0+5(10) -max {12+0,8+5,4+6,0+12}=13, u(10)=2
f3（ 9）=max｛10+f4（1）,5+f4（5）,0+f4（9）｝ =max｛10+0,5+6,0+6｝=11, u3（9）=1 f3（10）=max｛10+f4（2）,5+f4（6）,0+f4（10）｝ =max｛10+0,5+6,0+12｝=12, u3（10）=0 k=2 x2=0,2,4,6,8,10（吨） 注意：第2种货物重为3（吨/件），价值是4 （千元/件） 第1种货物重为2（吨/件），价值是3 （千元/件） f2（0）=f2（2）=0, u2（0）=u2（2）=0 f2（4）=max｛4+f3（1）,0+f3（4）｝=max｛4+0,0+5｝=5 u2（4）=0 f2（6）=max｛8+f3（0）,4+f3（3）,0+f3（6）｝ =max｛8+0,4+0,0+6｝=8, u2（6）=2 f2（8）=max｛8+f3（2）,4+f3（5）,0+f3（8）｝ =max｛8+0,4+6,0+10｝=10, u2（8）=0 f2（10）=max｛12+f3（1）,8+f3（4）,4+f3（7）,0+f3（10）｝ =max｛12+0, 8+5,4+6,0+12｝=13, u2（10）=2
k=1X=10 注意：第1种货物重为2（吨/件），价值是3（千元/件） 15+5(0) 15+0 12+5(2) 12+0 f(10) =max 9+6(4) =max 9+5=15 6+5(6) 6+8 3+5(8) 3+10 0+6(10) 0+13 u1(10)=5 至此，得卡车载货最大价值为15（千元），卡车最优 载货方案为：第一种货物装5件，其它货物均为0件
k=1 x1=10 注意：第1种货物重为2（吨/件），价值是3（千元/件） 15+f2（0） 15+0 12+f2（2） 12+0 f1（ 10）=max 9+f2（4）=max 9+5 =15 6+f2（6） 6+8 3+f2（8） 3+10 0+f2（10） 0+13 u1（10）=5 至此，得卡车载货最大价值为15（千元），卡车最优 载货方案为：第一种货物装5件，其它货物均为0件