请问数钱的贪婪算法怎样确保得到最优解?就是怎样一定得到最优解?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/28 09:14:40
请问数钱的贪婪算法怎样确保得到最优解?就是怎样一定得到最优解?
请问数钱的贪婪算法怎样确保得到最优解?
就是怎样一定得到最优解?
请问数钱的贪婪算法怎样确保得到最优解?就是怎样一定得到最优解?
贪婪算法：总是作出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,它所做出的仅是在某种意义上的局部最优解.
（注：贪婪算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题它能产生整体最优解.但其解必然是最优解的很好近似解.
基本思路：——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解.当达到某算法中的某一步不能再继续前进时,算法停止
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
基本要素：
1、 贪婪选择性质：所求问题的整体最优解可以通过一系列局部最优的选择,即贪婪选择来达到.（与动态规划的主要区别）
采用自顶向下,以迭代的方式作出相继的贪婪选择,每作一次贪婪选择就将所求问题简化为一个规模更小的子问题.
对于一个具体问题,要确定它是否具有贪婪选择的性质,我们必须证明每一步所作的贪婪选择最终导致问题的最优解.通常可以首先证明问题的一个整体最优解,是从贪婪选择开始的,而且作了贪婪选择后,原问题简化为一个规模更小的类似子问题.然后,用数学归纳法证明,通过每一步作贪婪选择,最终可得到问题的一个整体最优解.
2、最优子结构性质:包含子问题的最优解
1、 设有n个活动的安排,其中每个活动都要求使用同一资源,如演讲会场,而在同一时间只允许一个活动使用这一资源.每个活动都有使用的起始时间和结束时间.问：如何安排可以使这间会场的使用率最高.
活动 起始时间 结束时间
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14
算法：一开始选择活动1,然后依次检查活动一i是否与当前已选择的所有活动相容,若相容则活动加入到已选择的活动集合中,否则不选择活动i,而继续检查下一活动的相容性.即：活动i的开始时间不早于最近加入的活动j的结束时间.
Prodedure plan;
Begin
n:=length[e];
a {1};
j:=1;
for i:=2 to n do
if s[i]>=f[j] then
begin a a∪{i};
j:=i;
end
end;
例1 [找零钱] 一个小孩买了价值少于1美元的糖,并将1美元的钱交给售货员.售货员希望用数目最少的硬币找给小孩.假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币.售货员分步骤组成要找的零钱数,每次加入一个硬币.选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大.为保证解法的可行性（即：所给的零钱等于要找的零钱数）,所选择的硬币不应使零钱总数超过最终所需的数目.
假设需要找给小孩6 7美分,首先入选的是两枚2 5美分的硬币,第三枚入选的不能是2 5美分的硬币,否则硬币的选择将不可行（零钱总数超过6 7美分）,第三枚应选择1 0美分的硬币,然后是5美分的,最后加入两个1美分的硬币.
贪婪算法有种直觉的倾向,在找零钱时,直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）.可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）.