贪心选择性质证明(归纳步 部分背包问题 假设命题对k为真证明对k+1也为真 问题描述 算包盒=:了话动a…,根据归纳假设存在最 背包的重量限制为b iIES, sle n件物品,重量和价值分别为w,ⅵ,物品可以分 若425的最优解且12的请动比54米a 求满足背包重量限制的条件下,装入物品的最大 问题抽象 (题的最优a,a…,+D(e4+ 目标函数ma∑约束条件∑vx≤b 贪心思想 物品按照Ww进行排序,由高到低装入背包 其他背包问题 其他背包问题 ■考虑 ■ Loading问题 如果每种物品不止有一件(有限或无限件) n个集装箱12,…,n装上轮船,集装箱酌重 且可分割,能不能用贪心算法? 量W轮船装载重量限制为c,无体积限制 线性规划问题(目标函数和约束条件都是线 M≤c 性函数)一部分背包问题一贪心算法 ■0-1背包问题的限制形式:vi=1 整数规划问题(x均为非负整数)一一般 背包问题一搜索与剪枝/动态规划 贪心思想 将集装箱按照从轻到重排序,轻者先装 0-1规划问题-01背包问题一搜索与剪枝 证明:对问题规模进行归纳 /动态规划 经典贪心法 贪心法得到近似解 ■三个经典的贪心图算法(注意正确性证 ■地图着色问题 相邻的区域着不同的颜色,要求使用的颜色 Prim算法(最小生成树)(教材194页) 尽量少 对连接两个集合的最小边进行贪心选择 一般采用回溯法解决 Kruskal算法(最小生成树)(教材196页) 如果地图比较大,会采用贪心法求近似解 对连接两个集合的最小边进行贪心选择 ■不满足贪心选择性质,只能得到近似解 Dijkstra算法(单源最短路径)(教材187 页) ·选择下一个离单源最近的结点3 贪心选择性质证明（归纳步 骤） 假设命题对k为真,证明对k+1也为真. 算法执行到第k步, 选择了活动i1=1, i2, …, ik, 根据归纳假设存在最 优解A包含i1= 1, i2, … , ik, A中剩下的活动选自集合S’={ i | i∈S, si≥fk},且 A= {i1, i2, … , ik}∪B, B是S’的最优解. 若不然, S’的最优解为B*, B*的活动比B多，那么B*∪{1, i2, … , ik}是S 的最优解，且比A的活动多,与A 的最优性矛盾. 根据归纳基础，存在S’的最优解B’含有S’中的第一个活动，设为 ik+1, 且|B’|=|B|, 于是 {i1 , i2, … , ik} ∪ B’={i1 , i2, … , ik, ik+1} ∪(B’-{ik+1})也 是原问题的最优解. 部分背包问题 „ 问题描述 „ 背包的重量限制为b „ n件物品，重量和价值分别为wi，vi，物品可以分 割 „ 求满足背包重量限制的条件下，装入物品的最大 价值 „ 问题抽象 „ 目标函数 约束条件 „ 贪心思想 „ 物品按照vi/wi进行排序，由高到低装入背包 ∑= n i i i v x 1 max ∑= ≤ n i i i w x b 1 其他背包问题 „ 考虑 „ 如果每种物品不止有一件（有限或无限件） 且可分割，能不能用贪心算法？ „ 线性规划问题（目标函数和约束条件都是线 性函数） — 部分背包问题 — 贪心算法 „ 整数规划问题（xi均为非负整数） — 一般 背包问题 — 搜索与剪枝 / 动态规划 „ 0-1规划问题 — 0-1背包问题 — 搜索与剪枝 / 动态规划 其他背包问题 „ Loading问题 „ n个集装箱1,2,…,n 装上轮船，集装箱i的重 量wi, 轮船装载重量限制为c， 无体积限制. 问如何装使得上船的集装箱最多？不妨设 wi≤c. „ 0-1背包问题的限制形式 : vi=1 „ 贪心思想 „ 将集装箱按照从轻到重排序，轻者先装 „ 证明：对问题规模进行归纳 经典贪心法 „ 三个经典的贪心图算法（注意正确性证 明） „ Prim算法（最小生成树）（教材194页） „ 对连接两个集合的最小边进行贪心选择 „ Kruskal算法（最小生成树）（教材196页） „ 对连接两个集合的最小边进行贪心选择 „ Dijkstra算法（单源最短路径）（教材187 页） „ 选择下一个离单源最近的结点 贪心法得到近似解 „ 地图着色问题 „ 相邻的区域着不同的颜色，要求使用的颜色 尽量少 „ 一般采用回溯法解决 „ 如果地图比较大，会采用贪心法求近似解 „ 不满足贪心选择性质，只能得到近似解