资源描述：
《二维背包问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、二维背包问题上面讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过akg）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M不能超过a（kg），还要求旅行者背包的体积V不能超过b（m3）,我们把这样的问题称为“二维背包问题”。所谓“二维”是指在用动态规划处理时，它的状态变量有两个因素:一个是重量，一个是体积。二维背包问题的条件可概括为下表物品编号12……j……n－1n单位重量（kg）a1a2……aj……an-1an单位体积（m3）b1b2……bj……b
2、n-1bn单位价值c1c2……cj……cn-1cn二维背包问题可以归纳为如下形式的整数线性规划问题：max{c1x1+…+cixi+…+cnxn}a1x1+…+aixi+…+anxn≤ab1x1+…+bixi+…+bnxn≤bxi为非负整数，i=1，…，n正如课本叙述的一维背包问题那样，二维背包问题也可以用动态规划求解。蛇口码头有一艘载重量为30t，最大容为12×10m3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表:体积（10m3）重量（t）价值量A252B642C
3、363D474现求如何装载这四种货物使价值量最大。解：设xi（i=1，2，3，4）分别表示装载这四种货物的数量阶段k：将可装入的货物按1，2，…,n排序，每阶段装一种货物，共分为n个阶段。本题n＝4。状态变量Sk+1，Rk+1:在第k段开始时，背包允许装入的前k种物品的总重量和体积状态转移方程：Sk=Sk＋1-akxkRk＝Rk+1-bkxkfj（Sk，Rk）等于当背包中允许物品总重量不超过Sk（㎏）,且总体积不超过Rk（m3）,采取最优策略只装前j种物品时的最大使用价值（j=1，2，…，n）。maxz=2x
4、1+2x2+3x3+4x4体积（10m3）重量（t）价值量A252B642C363D4742x1+6x2+3x3+4x4≤12S.t5x1+4x2+6x3+7x4≤30xi为非负整数（i=1，2，3，4）根据题意我们有：用动态规划逆序法求解如下：当k=4时f4(12,30)=max{2x1+2x2+3x3+4x4}2x1+6x2+3x3+4x4≤125x1+4x2+6x3+7x4≤30xi为非负整数（i=1，2，3，4）=max{4x4+max(2x1+2x2+3x3)}12-4x4≥02x1+6x2+3x3
5、+4x4≤1230-7x4≥05x1+4x2+6x3+7x4≤30x4为非负整数xi为非负整数（i=1，2，3，4）=max{4x4+f3(12-4x2,30-7x4)}x4≤3x4≤30/7x4为非负整数=max{0+f3(12,30),4+f3(8,23),8+f3(4,16),12+f3(0,9)当k=3f3(12,30)=max{2x1+2x2+3x3}2x1+6x2+3x3≤125x1+4x2+6x3≤30xi为非负整数=max{3x3+f2(12-3x3,30-6x3)}12-3x3≥030-6x
6、3≥0x3为非负整数=max{0+f2(12,30),4+f2(9,24),6+f2(6,18),9+f2(3,12),12+f2(0,6)}=max{3x3+f2(8-3x3,23-6x3)}8-3x3≥023-6x3≥0x3为非负整数f3(8,23)=max{0+f2(8,23),3+f2(5,17),6+f2(2,11)}同理：f3(12,30)=max{0+f2(4,16),3+f2(1,10)}f3(0,9)=f2(0,9)当k=2时f2(12,30)=max{2x1+2x2}2x1+6x2≤125
7、x1+4x2≤30xi为非负整数=max{2x2+max(2x1)}x2≤2x2≤15/2X2为非负整数=max{0+f1(12,30),2+f1(6,26),4+f1(0,22)}同理：f2(9,24)=max{0+f1(9,24),2+f1(3,20)}f2(6,18)=max{0+f1(6,18),2+f1(0,14)}f2(3,12)=f1(3,12)f2(0,6)=f1(0,6)f2(8,23)=max{0+f1(8,23),2+f1(2,19)}f2(5,17)=f1(5,17)f2(2,11)=
8、f1(2,11)f2(4,16)=f1(4,16)f2(1,10)=f1(1,10)f2(0,9)=f1(0,9)当k=1时f1(12,30)=max{2x1}=max{2x1}=122x1≤12x1=0,1,2,3,4,5,65x1≤30xI为非负整数同理可得f1(6,26)6f1(0,22)0f1(9,24)8f1(3,20)2f1(6,18)6f1(0,14))0f1(3,12)2f1(0,6
