动态规划在经济管理中 的应用一0-1背包问题 补充:动态规划 >背包问题的扩展:0-1背包问题 某人准备外出旅游,行装中有A、B、C、D、E共5件备 选物品,其重量和价值如表所示,假定行李总重不得 超过13Kg,求总价值最大的行李构成方案。 物品 ABCDE 数学模型: 重量Kg7543 设x为第i种物品是否装入(1-是,0- 价值百元94320.5 否),则0-1整数规划模型: 目标(总价值最大): MaxP=9x1+4x2+3x3+2x4+0.5x5 重量约束:7x1+5x2+4x3+3x4+x≤13 0-1约束:x为0或1(=1,2,3,4,5) RuC Information School, Ye Xiang, 2007补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－0-1背包问题 ➢ 背包问题的扩展：0-1背包问题 某人准备外出旅游，行装中有A、B、C、D、E共5件备 选物品，其重量和价值如表所示，假定行李总重不得 超过13Kg，求总价值最大的行李构成方案。 物品 A B C D E 重量/Kg 7 5 4 3 1 价值/百元 9 4 3 2 0.5 数学模型： 设xi为第i种物品是否装入（1-是，0- 否），则0-1整数规划模型： 目标(总价值最大)： Max P=9x1+4x2+3x3+2x4+0.5x5 重量约束：7x1+5x2+4x3 +3x4+x513 0-1约束：xi为0或1（i=1,2,3,4,5）