动态规划在经济管理中 的应用一背包问题 补充:动态规划 例2:背包问题 位旅行者携带背包去登山,已知他所能承受的背包重量限度为a千 克,现有n种物品可供他选择装入背包,第种物品的单件重量为a1千 克,其价值(可以是表明本物品对登山的重要性的数量指标)是携 带数量x的函数c;x;(i=1,2,…,n),问旅行者应该如何选择携带 各种物品的件数,以使总价值最大?(背包问题等同于车、船、人造 卫星等工具的最优装载等,有广泛的实际意义) 代数模型(一维背包问题): 设x1为第i物品装入的件数,则整数规划模型: 目标(总价值最大):MaxP=Σcr1 总重量约束:∑a1x;≤a 非负约束:x1≥0且为整数(i=1,2,…,n) 在 Excel中的解法:用本书9.1节的一般整数规划 >背包问题的扩展 当x仅表示装入(取1)和不装(取0)第种物品,则本模型就是0-1背包 问题。 多维背包问题:当约束条件不止一个时,如多总体积的限制等 RuC Information School, Ye Xiang, 2007补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－背包问题 ➢ 例2：背包问题 ❖ 一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a千 克，现有n种物品可供他选择装入背包，第i种物品的单件重量为ai千 克，其价值（可以是表明本物品对登山的重要性的数量指标）是携 带数量xi的函数cixi（i=1，2，…，n），问旅行者应该如何选择携带 各种物品的件数，以使总价值最大？(背包问题等同于车、船、人造 卫星等工具的最优装载等，有广泛的实际意义) 代数模型（一维背包问题）： 设xi为第i种物品装入的件数，则整数规划模型： 目标(总价值最大)：Max P=cixi 总重量约束： aixi a 非负约束：xi  0 且为整数（i=1，2，…，n） 在Excel中的解法：用本书9.1节的一般整数规划 ➢ 背包问题的扩展 ➢ 当xi仅表示装入(取1)和不装(取0)第i种物品，则本模型就是0-1背包 问题。 ➢ 多维背包问题：当约束条件不止一个时，如多总体积的限制等