第五章 动态规划详解.ppt

动态规划法解01背包 动态规划法解01背包 问题描述 已知：n 个重量 w1,...,wn、价值 v1,...,vn 的物品和一个承重量W的背包。 要求：找出最有价值子集，且能装入背包中（不超重）。 假定：物品重量、背包承重量、物品数量（01背包）都是整数。 01背包的最优化描述：（xi = 0：i 物品不装入， xi = 1：i 物品装入） 求满足约束方程的是目标函数达到最大的解向量 X = (x1 , ... , xn) 。 穷举n个物品全部组合（幂集，子集数=2n），从中找出最有价值子集。 贪婪法不一定能找到最优解。 物品数 承重量 动态规划法求解01背包 动态规划法求解01背包 分段： 动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解 由直接前趋子实例解计算得到。对于01背包问题，可利用减一技术和 最优性原则，按物品数量和背包承重量分段。 V(i, j) —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。 前 i 个物品中最优子集的总价值（动态规划函数）： V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0） V(i, j) = V(i-1, j) 第 i 个物品不能装入， j wi （超重） V(i, j) = max { vi+V(i-1, j-wi ) , V(i-1, j) } j wi （不超重） i在最优子集中 i不在最优子集中 自底向上计算：V(i, j)→V(n, W) （i：0→n, j：0→W）目标 V(n, W) 第1阶段：装入1个物品，计算各种承重量下的最优价值子集； 第2阶段：装入2个物品，计算各种承重量下的最优价值子集； 第n阶段：装入n个物品，计算各种承重量下的最优价值子集。 动态规划法解01背包问题的算法表 动态规划法解01背包问题的算法表： 前 i 个物品中最优子集的总价值（动态规划函数）： V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0） V(i, j) = V(i-1, j) 第 i 个物品不能装入， j wi （超重） V(i, j) = max { vi+V(i-1, j-wi ) , V(i-1, j) } j wi （不超重） i在最优子集中 i不在最优子集中 V j=0 ...... j - wi ...... j ...... j=W i=0 0 ... 0 ... 0 ... 0 ... ... i - 1 0 V(i-1, j-wi) V(i-1, j) i 0 V(i, j) ... ... i=n 0 V(n, W) 说明：可按行（或列）填写此表。 目标 动态规划法解01背包问题算例 动态规划法解01背包问题算例 例：01背包数据如下表，求：能够放入背包的最有价值的物品集合。 物品 i 重量 wi 价值 vi 承重量 W 1 w1=2 v1=12 W=5 2 w2=1 v2=10 3 w3=3 v3=20 4 w4=2 v4=15 V j=0 1 2 3 4 5 i=0 0 0 0 0 0 0 1 0 0 12 12 12 12 2 0 10 12 22 22 22 3 0 10 12 22 30 32 4 0 10 15 25 30 37 自底向上：按行或列填表。递推公式： 例如： 接下来，找出最优解的物品集合。 动态规划法解01背包问题算例（续） 通过最优解的回溯，找出最优子集为 { w1 , w2 , w4 } 最优解有w4 最优解无w3 最优解有w2 最优解有w1 最 优 解 回 溯 2 01背包的动态规划算法（带记忆功能） 01背包的动态规划算法（带记忆功能） 算法递推式： V(i, j) = max { V(i-1, j), vi+V(i-1, j-wi) } 交叠子问题： 直接用递推式设计递归算法，产生交叠子问题，重复计算公共子问题，算法效率低下（指数级甚至更差）。 避免交叠子问题的递归算法： 递归过程（内层为更小子问题）是自顶向下的（规模减小），缺点是 将产生交叠子问题。动态规划算法采用自