C++c语言贪心算法ppt课件

1、本次课程的主要内容本次课程的主要内容贪心算法贪心算法贪心算法1 1、什么是贪心算法、什么是贪心算法: :贪心算法又称贪婪算法是指，在对问题求解时，总是做出贪心算法又称贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。优解或

2、者是整体最优解的近似解。 2 2、基本思路、基本思路(1)(1)建立数学模型来描述问题。建立数学模型来描述问题。 (2) (2)把求解的问题分成若干个子问题。把求解的问题分成若干个子问题。 (3) (3)对每一子问题求解，得到子问题的局部最优解。对每一子问题求解，得到子问题的局部最优解。 (4) (4)把子问题的解局部最优解合成原来解问题的一个解。把子问题的解局部最优解合成原来解问题的一个解。 3 3、算法实现。、算法实现。(1)(1)从问题的某个初始解出发。从问题的某个初始解出发。(2)(2)采用循环语句，当可以向求解目标前进一步时，就根据局部最优采用循环语句，当可以向求解目标前进一步时，就

3、根据局部最优策略，得到一个部分解，缩小问题的范围或规模。策略，得到一个部分解，缩小问题的范围或规模。(3)(3)将所有部分解综合起来，得到问题的最终解。将所有部分解综合起来，得到问题的最终解。贪心算法贪心算法-例题分析例题分析例题例题1、背包问题背包问题 有一个背包，背包容量是有一个背包，背包容量是M=150。有。有7个物品，物品可以分割成任意大小。要个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品物品 ：A B C D E F G 分量分量 ：35 30 60 50 40 10 25 价值

4、价值 ：10 40 30 50 35 40 30 分析：分析：目标函数：目标函数： pi最大最大约束条件是装入的物品总重量不超过背包容量：约束条件是装入的物品总重量不超过背包容量：wi=M( M=150) （1根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？（2每次挑选所占空间最小的物品装入是否能得到最优解？每次挑选所占空间最小的物品装入是否能得到最优解？（3每次选取单位容量价值最大的物品，成为解本题的策略。每次选取单位容量价值最大的物品，成为解本题的策略。 根据以上的分析我们就可以得到解决本题的策略。即单

5、位容量最大的物品。根据以上的分析我们就可以得到解决本题的策略。即单位容量最大的物品。贪心算法贪心算法-例题分析例题分析例题例题1算法实现：算法实现： 在算法的实现上应该不是很难，只要我们算出每个物品在单位容量上的价值在算法的实现上应该不是很难，只要我们算出每个物品在单位容量上的价值就行，然后再使用一个排序的算法，将其从大到小排序。然后再根据背包当前剩就行，然后再使用一个排序的算法，将其从大到小排序。然后再根据背包当前剩下的容量来选取本次物品的重量。如果背包的容量比当前武平的容量要大，那么下的容量来选取本次物品的重量。如果背包的容量比当前武平的容量要大，那么就将当前物品全部装进去。如果不够，那么

6、就将当前物品切割装进去。然后就可就将当前物品全部装进去。如果不够，那么就将当前物品切割装进去。然后就可以跳出循环。这里我们在存储数据时为了方便起见可以使用一个结构体的方式来以跳出循环。这里我们在存储数据时为了方便起见可以使用一个结构体的方式来存储。结构体里面保存物品的重量，价值，以及单位质量的价值。然后使用存储。结构体里面保存物品的重量，价值，以及单位质量的价值。然后使用sort函数来排序，排序时我们只要重写函数来排序，排序时我们只要重写sort函数里面的比较函数即可。函数里面的比较函数即可。Sort(p,p+n,Up)。P使我们保存物品的结构体。使我们保存物品的结构体。N是物品的总数。是物品

7、的总数。Up使我们自定使我们自定义的排序方法。义的排序方法。贪心算法贪心算法-例题例题1代码代码贪心算法贪心算法-例题分析例题分析例题例题2：活动安排：活动安排标题：标题： 设有设有n个活动的集合个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使都有一个要求使用该资源的起始时间用该资源的起始时间si和一个结束时间和一个结束时间fi,且且si fi 。要求设计程序，使得安排的活动。要求设计程序，使得安排的活动最

8、多。最多。分析：分析： 活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一个简单、漂亮的方法，使尽可能多的活动能兼容的使用公共资源。设有个简单、漂亮的方法，使尽可能多的活动能兼容的使用公共资源。设有n个活动的集个活动的集合合0，1，2，n-1，其中每个活动都要求使用同一资源，如会场等，而在同，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始都有一个要求使用该资源的起始时间时间starti和一个

9、结束时间和一个结束时间endi，且，且startij的部分。的部分。演示算法实现过程。演示算法实现过程。人工模拟人工模拟1234555666最小生成树的耗费为最小生成树的耗费为15算法难点算法难点从刚才的演示过程，可知算法实现有两个难点：（1边的选择要求从小到大选择，则开始显然要对边进行升序排序。（2选择的边是否需要，则从判断该边加入后是否构成环入手。难点解决一）难点解决一）（1 1对边升序排序对边升序排序 方法可根据以前方法可根据以前 中选择合适的排序。中选择合适的排序。 在此采用链式结构，通过插入排序完成。在此采用链式结构，通过插入排序完成。 每一结点存放一条边的左右端点序号、权值及后继结点指针。每一结点存放一条边的左右端点序号、权值及后继结点指针。难点解决二）难点解决二）（2 2边的加入是否构成环边的加入是否构成环 一开始假定各顶点分别为一组，其组号为端点序号。一开始假定各顶点分别为一组，其组号为端点序号。 选择某边后，看其两个端点是否在同一组中，即所在组号是否相同选择某边后，看其