本文介绍: – 贪心选择特性:全局的最优解可以通过局部的最优(贪婪) 选择得到.• 动态规划需要检查子问题的解。– 最优子结构: 问题的最优解包含了其子问题的最优解.• 例如, 如果 A 是S的最优解, 那么 A ‘ = A – {1} 是 的最优解.• 贪心算法 (试探) 并不能总是得到最优解.

全局的最优解可以通过局部的最优(贪婪) 选择得到.

– 最优子结构: 问题的最优解包含了其子问题的最优解.

• 例如, 如果 A 是S的最优解, 那么 A ‘ = A – {1} 是 的S'={iin S:s_{i} >=f_{1} }最优解.

• 贪心算法 (试探) 并不能总是得到最优解.

– 相同: 最优子结构

– 差别: 贪婪选择特性

给定一个集合 S = {1, 2, …, n} n个计划的活动,对每个活动 i, 开始时间为 s_{i} 结束时间为 f_{i}, 选择出相互兼容的活动最大集合.

– 活动 i 和j兼容 如果 [s_{i},f_{i}) 和 [s_{j},f_{j}) 不重叠(i.e.,s_{i}ge{f_{j}} or s_{j}ge{f_{i}})

问题分析

基本思想

 对应伪代码

贪心选择性质证明

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注