贪心策略 - 贪心策略.ppt

局部利益最大化? 0-1 背包问题:有 n个物品,每个物品 i有它的重量 w i和价值 v i,现在有一个可以承重 W 的背包,问如何选择那些物品装入背包使得他的价值最大,而且不超过背包承重的限制。有n个数对,如何选择这些数对的一个子集 S,使得前提下, 的值达到最大 Ww Si i?????Si iv )1(),(nivw ii??如果我们可以将物品分割,选择把物品的一部分放入背包? 如果我们可以将物品分割,选择把物品的一部分放入背包? 优先选择重量最轻的物品优先选择重量最轻的物品优先选择价值最大的物品优先选择价值最大的物品优先选择性价比最高的物品优先选择性价比最高的物品不会出现装不满的情况不会出现装不满的情况比如我们现在要装的不是 n件物品,而是发现有 n堆的金币、银币、宝石、珍珠。。。比如我们现在要装的不是 n件物品,而是发现有 n堆的金币、银币、宝石、珍珠。。。局部最优整体最优局部最优整体最优相互关系希望得到动态规划贪心策略贪心算法总是作出在当前看来最好的选择, 希望得到的最终结果也是整体最优的贪心算法总是作出在当前看来最好的选择, 希望得到的最终结果也是整体最优的需要证明局部最优能够导致整体最优需要找出整体最优和局部最优的最优子结构设有 n个互斥的活动要使用同一资源,每个活动都有一个起始时间 si和一个结束时间 fi. 两个活动 i、j,如果满足 si≥fj或者或sj≥fi,则称相容的能否设计一种算法,使得有尽量多的活动使用这个资源 sj fj si fi 优先选择最早开始的优先选择最早开始的优先选择占用时间最短的优先选择占用时间最短的优先选择和其他互斥最少的优先选择和其他互斥最少的优先选择最早完成的活动,这样可以给安排其他活动剩余更多的时间优先选择最早完成的活动,这样可以给安排其他活动剩余更多的时间原始状态第一步第二步第三步第四步如果最后一个选择此活动也是一个最优解如果最后一个选择此活动也是一个最优解贪心算法只是希望得到的解是最优解, 而并不能得到所有的最优解贪心算法只是希望得到的解是最优解, 而并不能得到所有的最优解由此得到的集合是相容的由此得到的集合是相容的假设 S是我们得到的集合, O是任意一个最优解, S中的第 k个活动的结束时间早于 O中第 k个活动的结束时间假设 S是我们得到的集合, O是任意一个最优解, S中的第 k个活动的结束时间早于 O中第 k个活动的结束时间贪心算法返回一个最优解贪心算法返回一个最优解我们记 i k为S中第 k个活动, j k为O中第 k个活动,用数学归纳法显然 f(i 1 ) <= f(j 1)假设 f(i k-1 ) <= f(j k-1),我们证明 f(i k ) <= f(j k) 由于 f(i k-1 ) <= f(j k-1),所以集合中与 S的前 k-1 个相容个活动一定包含与 O的前 k-1 个相容个活动,根据我们选择最早结束的相容活动,所以 f(i k ) <= f(j k) 贪心法的领先概念:贪心法的每一步做的都比一个最优解好,所以他也是最优解贪心法的领先概念:贪心法的每一步做的都比一个最优解好,所以他也是最优解设有 n个互斥的活动要使用同一资源,每个活动都更加灵活, 我们不规定他的具体起始时间和终止时间,而是确定一个最后期限(截止时间 deadline)di , 要求在这个期限内完成,第 i个活动需要 ti的连续时间来完成能否设计一种算法,使得所有被延迟的活动中最大的延迟时间最小 ti ti tj tj di dj 能否设计一种算法,使得所有被延迟的活动中最大的延迟时间最小 1 12 23 3 2541 12 23 33延迟了 1个时间单位 1 13 32 2 2延迟了 2个时间单位 2 21 13 3 3延迟了 1个时间单位, 1延迟了 1个时间单位 2 21 13 3 1延迟了 4个时间单位 1 12 23 3 2延迟了 2个时间单位, 1延长了 2个时间单位 1 12 23 32延迟了 1个时间单位, 1延长了 4个时间单位这两种方法有什么特点,或者其中一个有什么规律