本文介绍: – 贪心选择特性:全局的最优解可以通过局部的最优(贪婪) 选择得到.• 动态规划需要检查子问题的解。– 最优子结构: 问题的最优解包含了其子问题的最优解.• 例如, 如果 A 是S的最优解, 那么 A ‘ = A – {1} 是 的最优解.• 贪心算法 (试探) 并不能总是得到最优解.
什么时候使用贪婪算法?
– 贪心选择特性:
全局的最优解可以通过局部的最优(贪婪) 选择得到.
• 动态规划需要检查子问题的解。
– 最优子结构: 问题的最优解包含了其子问题的最优解.
• 例如, 如果 A 是S的最优解, 那么 A ‘ = A – {1} 是 的最优解.
• 贪心算法 (试探) 并不能总是得到最优解.
• 谈论算法和动态规划 (DP)对比
– 相同: 最优子结构
– 差别: 贪婪选择特性
活动选择问题
问题分析
基本思想
对应伪代码
贪心选择性质证明
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。