计算机算法设计与分析 简述什么是贪心选择性质
1个回答
展开全部
贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来得到.
就是说,你需要证明当前问题可以通过选择最好的那个元素（比如01背包,总能够通过选择当前重量最小的物品来得到最优解）来解决问题
证明：（每一步所做的贪心选择最终导致问题的整体最优解）
//基本思路：考察一个问题的最优解,证明可修改该最优解,使得其从贪心选择开始,然后用数学归纳法证明每一步都可以通过贪心选择得到最优解
1,假定首选元素不是贪心选择所要的元素,证明将首元素替换成贪心选择所需元素,依然得到最优解；
2,数学归纳法证明每一步均可通过贪心选择得到最优解
就是说,你需要证明当前问题可以通过选择最好的那个元素（比如01背包,总能够通过选择当前重量最小的物品来得到最优解）来解决问题
证明：（每一步所做的贪心选择最终导致问题的整体最优解）
//基本思路：考察一个问题的最优解,证明可修改该最优解,使得其从贪心选择开始,然后用数学归纳法证明每一步都可以通过贪心选择得到最优解
1,假定首选元素不是贪心选择所要的元素,证明将首元素替换成贪心选择所需元素,依然得到最优解；
2,数学归纳法证明每一步均可通过贪心选择得到最优解
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
