算法设计(eclipse编写贪心算法设计活动安排)

实验报告
课程名称：算法设计与分析实验名称：贪心法解活动安排问题任课教师：专业：计算机科学与技术
班级: 20xx 级x班学号：
姓名：完成日期： 20xx年x月xx日
五、实验总结
在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

经过修正后，自己真正理解了贪心法解活动安排问题的原理，重新完成本次实验内容也是很顺利，在编程方面没有遇到什么困难。

贪心算法流程图贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法，以期望能够获得全局最优解。

在实际应用中，贪心算法通常用来解决最优化问题，比如最小生成树、哈夫曼编码等。

贪心算法的流程图可以帮助我们更直观地理解其工作原理和实现过程。

首先，我们来看一下贪心算法的流程图。

在图中，首先我们需要确定问题的解空间，然后根据问题的特点选择合适的贪心策略。

接着，我们需要确定每一步的最优选择，并且不断更新当前状态，直到达到最优解或者无法继续优化为止。

在实际应用中，贪心算法的流程图可以根据具体问题的特点进行调整和优化。

下面我们以一个简单的例子来说明贪心算法的流程图。

假设现在有一组活动，每个活动都有一个开始时间和结束时间，我们希望安排尽可能多的活动，使得它们之间不会相互冲突。

这个问题可以用贪心算法来解决。

首先，我们需要对活动按照结束时间进行排序，然后从第一个活动开始，依次检查每个活动的开始时间是否晚于上一个活动的结束时间。

如果是，则将该活动加入最优解集合中，并更新当前状态。

如果不是，则将该活动舍弃。

通过这样的贪心策略，我们可以得到安排最多活动的最优解。

整个流程可以用一个简单的流程图来表示，从而更直观地理解贪心算法的工作原理。

贪心算法的流程图不仅可以帮助我们理解算法的实现过程，还可以指导我们在实际应用中进行调整和优化。

通过对问题解空间的划分和贪心策略的选择，我们可以更快地找到最优解，提高算法的效率和性能。

总之，贪心算法的流程图是我们理解和应用贪心算法的重要工具，它可以帮助我们更直观地理解算法的工作原理，指导我们进行问题求解和算法优化。

希望通过本文的介绍，读者能对贪心算法有一个更深入的理解，并在实际应用中取得更好的效果。

贪心算法程序设计贪心算法程序设计1. 什么是贪心算法贪心算法（Greedy Algorithm）是一种常见的算法思想，它在每一步选择中都采取当前状态下的最优选择，从而希望最终达到全局最优解。

贪心算法的核心思想是局部最优解能导致全局最优解。

2. 贪心算法的基本步骤贪心算法的基本步骤如下：1. 定义问题的优化目标。

2. 将问题分解成子问题。

3. 选择当前最优的子问题解，将子问题的解合并成原问题的解。

4. 检查是否达到了问题的优化目标，如果没有达到，则回到第二步，继续寻找下一个最优子问题解。

5. 在所有子问题解合并成原问题解后，得到问题的最优解。

3. 贪心算法的应用场景贪心算法的应用非常广泛，几乎可以用于解决各种优化问题。

以下几个常见的应用场景：1. 零钱找零问题：给定一定面额的纸币和硬币，如何找零使得所需纸币和硬币的数量最小？2. 区间调度问题：给定一些活动的开始时间和结束时间，如何安排活动使得可以办理的活动数量最大？3. 背包问题：给定一些具有重量和价值的物品，如何选择物品使得背包的总价值最大？4. 最小树问题：给定一个带权无向图，如何找到一棵树，使得它的边权之和最小？5. 哈夫曼编码问题：给定一组字符和相应的频率，如何构造一个满足最低编码长度限制的二进制编码？4. 贪心算法的优缺点贪心算法的优点是简单、高效，可以快速得到一个近似最优解。

而且对于一些问题，贪心算法能够得到全局最优解。

贪心算法的缺点在于它不一定能够得到全局最优解，因为在每一步只考虑局部最优解，无法回溯到之前的选择。

5. 贪心算法的程序设计在使用贪心算法进行程序设计时，通常需要以下几个步骤：1. 定义问题的优化目标。

2. 将问题分解成子问题，并设计子问题的解决方案。

3. 设计贪心选择策略，选择局部最优解。

4. 设计贪心算法的递推或迭代公式。

5. 判断贪心算法是否能够得到全局最优解。

6. 编写程序实现贪心算法。

6.贪心算法是一种常见的算法思想，它在每一步选择中都采取当前状态下的最优选择，从而希望最终达到全局最优解。

浅谈Python实现贪⼼算法与活动安排问题贪⼼算法原理：在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪⼼算法不是对所有问题都能得到整体最优解，但对范围相当⼴泛的许多问题他能产⽣整体最优解或者是整体最优解的近似解。

特性：贪⼼算法采⽤⾃顶向下，以迭代的⽅法做出相继的贪⼼选择，每做⼀次贪⼼选择就将所求问题简化为⼀个规模更⼩的⼦问题，通过每⼀步贪⼼选择，可得到问题的⼀个最优解，虽然每⼀步上都要保证能获得局部最优解，但由此产⽣的全局解有时不⼀定是最优的，所以贪婪法不要回溯。

能够⽤贪⼼算法求解的问题⼀般具有两个重要特性：贪⼼选择性质和最优⼦结构性质。

如题：给出⼀组活动，告诉每个活动的开始时间和结束时间，要求出算出能参加的最多活动的数量或者活动的起⽌时间贪⼼算法思路：⽤两个数组s，f分别存储活动的起⽌时间，根据活动的结束时间对活动进⾏⼀个⾮减的活动序列，同样活动的开始时间list也要做对应的调整，这⾥博主是通过冒泡排序同步交换的，举例：活动（1，4）（2，3）（3，5）那么我们得到的s = [2,1,3]f = [3,4,5]通过⽐较下⼀个活动的开始时间与上⼀个活动的结束时间的⼤⼩关系，确定这两个活动是否是相容的，如果开始时间⼤于结束时间，则相容，反之不相容,代码如下#⽤冒泡排序对结束时间进⾏排序，同时得到对应的开始时间的listdef bubble_sort(s,f):for i in range(len(f)):for j in range(0,len(f)-i-1):if f[j] > f[j+1]:f[j], f[j+1] = f[j+1],f[j]s[j],s[j+1] = s[j+1],s[j]return s,fdef greedy(s,f,n):a = [True for x in range(n)]#初始选择第⼀个活动j = 0for i in range(1,n):#如果下⼀个活动的开始时间⼤于等于上个活动的结束时间if s[i] >= f[j]:a[i] = Truej = ielse:a[i] = Falsereturn an = int(input())arr = input().split()s = []f = []for ar in arr:ar = ar[1:-1]start = int(ar.split(',')[0])end = int(ar.split(',')[1])s.append(start)f.append(end)s,f = bubble_sort(s,f)A = greedy(s,f,n)res = []for k in range(len(A)):if A[k]:res.append('({},{})'.format(s[k],f[k]))print(' '.join(res))执⾏结果如下：输⼊11个活动的起⽌时间，输出相容的活动的起⽌时间以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

贪心算法程序设计贪心算法程序设计1、简介1.1 算法概述贪心算法是一种在每一步都做出局部最优选择的算法，以期达到全局最优。

贪心算法通常适用于问题具有最优子结构的情况，即问题的最优解包含了其子问题的最优解。

1.2 算法流程贪心算法的通用流程如下：1、初始化：选择一个初始解。

2、选择：从问题的解空间中选择一个局部最优解。

3、约束：验证选择的解是否满足问题的约束条件。

4、更新：更新问题的解空间，继续迭代选择、约束和更新操作，直到满足问题的结束条件。

2、贪心算法的经典问题2.1 零钱找零问题给定一个金额和硬币的面额列表，找到凑成该金额所需的最少硬币数。

步骤：1、初始化一个空的结果列表。

2、将硬币面额列表按从大到小的顺序排序。

3、从硬币面额最大的开始，尽量选择面额最大的硬币，直至不能选择为止。

4、如果当前选择的硬币可以凑成金额，则将该硬币加入结果列表，并将金额减去该硬币的面额。

5、重复步骤3和4，直到金额为0。

6、返回结果列表的长度即为所需的最少硬币数。

2.2 区间覆盖问题给定一个区间列表，选择最少的区间，使得这些区间能够覆盖整个目标区间。

步骤：1、将区间列表按照结束值从小到大排序。

2、初始化一个空的结果列表，用于存储选择的区间。

3、遍历排序后的区间列表，选择第一个结束值最小的区间，并将其加入结果列表。

4、遍历剩余的区间，如果当前区间的起始值大于已选择的最后一个区间的结束值，则将该区间加入结果列表。

5、返回结果列表。

3、贪心算法的优缺点3.1 优点- 简单性：贪心算法通常都比较直观简单，易于理解和实现。

- 效率高：贪心算法通常时间复杂度较低，能够在线性时间内求解问题。

3.2 缺点- 局部最优解：贪心算法只考虑每一步的局部最优解，而不考虑全局最优解。

因此，在某些问题上，贪心算法可能无法得到最优解。

- 缺乏验证：贪心算法没有对解的可行性进行全局验证，因此不能保证求得的解是问题的最优解。

4、附件本文档不涉及附件。

1.引言：贪心法是一种改进了的分级处理方法。

用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。

每一步只考虑一个数据，它的选取满足局部优化条件。

若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。

这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。

贪心算法总是做出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。

2.贪心算法的基本思想及存在问题贪心法的基本思想：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当达到某算法中的某一步不能再继续前进时，算法停止。

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

3.活动安排问题：3.1 贪心算法解决活动安排问题学校举办活动的安排问题是用贪心算法有效求解的一个很好例子。

活动安排问题要求安排一系列争用某一公共资源的活动。

用贪心算法可使尽可能多的活动能兼容的使用公共资源。

设有n个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且starti<endi。

如选择了活动i，则它在半开时间区间[starti,endi）内占用资源。

若区间[starti,endi)与区间[startj,endj)不相交，称活动i与活动j是相容的。

也就是说，当start j≥endi或starti≥endj时，活动i与活动j相容。

活动安排问题就是在所给的活动集合中选出最大的相容子活动集合。

C++贪⼼算法实现活动安排问题（实例代码）贪⼼算法贪⼼算法（⼜称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

具体代码如下所⽰：#include <cstdio>#include <iostream>#include <ctime>#include <windows.h>#include <algorithm>#include <fstream>using namespace std;struct activity{int no;int start;int finish;};bool cmp(const activity &x, const activity &y){return x.finish<y.finish;//从⼩到⼤排<，若要从⼤到⼩排则>}int greedySelector(int m,int solution[],struct activity activity[]){int number = 1;solution[0] = 1;int i,j = 0,counter = 1;for(i = 1;i < m ;i++){if(activity[i].start >=activity[j].finish){solution[i] = 1;j = i;counter++;}elsesolution[i] = 0;}cout << "The amount of activities is:"<<counter<<endl;cout << "The solution is:";for(i = 0 ;i < m ;i++){if (solution[i] == 1){cout << activity[i].no <<" ";}}return counter;}int main(void){LARGE_INTEGER nFreq;LARGE_INTEGER nBeginTime;LARGE_INTEGER nEndTime;ofstream fout;srand((unsigned int)time(NULL));int m,i,j,t;double cost;cout << "Please enter the number of times you want to run the program:";cin >> t;fout.open("activity.txt",ios::app);if(!fout){cerr<<"Can not open file 'activity.txt' "<<endl;return -1;}fout.setf(ios_base::fixed,ios_base::floatfield); //防⽌输出的数字使⽤科学计数法for (j = 0;j < t;j++){cout << "——————————————————The "<< j + 1 << "th test —————————————————"<<endl;m = 1 + rand()%100000;fout<<m<<",";int solution[m];activity activity[m];for( i = 0;i < m;i++){activity[i].no = i+1;activity[i].start = 1 + rand()%1000;while(1){activity[i].finish = 1 + rand()%10000;if(activity[i].finish > activity[i].start) break;}}QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);sort(activity,activity+m,cmp);greedySelector(m,solution,activity);QueryPerformanceCounter(&nEndTime);cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;fout << cost << endl;cout << "\nThe running time is:" << cost << " s" << endl;}fout.close();cout << endl << endl;cout << "Success!" << endl;return 0;}总结以上所述是⼩编给⼤家介绍的C++贪⼼算法实现活动安排问题，希望对⼤家有所帮助，如果⼤家有任何疑问请给我留⾔，⼩编会及时回复⼤家的。

贪心算法程序设计贪心算法程序设计一、什么是贪心算法贪心算法是一种常见的算法设计思想，其基本思想是通过每一步的最优选择，最终得到全局最优解。

贪心算法通常适用于求解最优化问题，该问题可以分解为一系列子问题，并且每个子问题的最优解能够推导出整个问题的最优解。

二、贪心算法的特点贪心算法具有以下特点：1. 贪心选择性质：即每一步选择都是当前状态下的最优选择，不考虑的后果；2. 最优子结构性质：即问题的最优解包含了子问题的最优解；3. 无后效性：即当前选择的结果不会影响后续的选择。

贪心算法的优势在于其简单性和高效性，但也存在一些问题：1. 局部最优解：由于贪心算法每步只考虑局部最优解，有可能导致得到的整体解并非全局最优解；2. 问题依赖：贪心算法适用于特定类型的问题，不适用于所有问题。

三、贪心算法的应用举例1. 区间调度问题给定一个任务列表，每个任务有一个开始时间和结束时间，任务之间不能进行。

目标是选择尽可能多的任务进行安排。

贪心算法的思路是每次选择最早结束的任务作为当前任务。

def interval_schedule(intervals):intervals.sort(key=lambda x: x[1]) 根据结束时间排序count = 1 计数器，记录安排的任务数目end = intervals[0][1] 记录当前最晚结束时间for interval in intervals:if interval[0] >= end: 当前任务的开始时间在之前的任务结束时间后，可以安排count += 1end = interval[1]return count2. 零钱兑换问题给定一个金额和一些面额不同的硬币，要求用最少数量的硬币组合达到指定的金额。

贪心算法的思路是每次选择面额最大的硬币。

但要注意，贪心算法并不一定能得到最优解，面额为{1, 5, 11}的硬币，要找零金额为15时，贪心算法会选择11 + 1 + 1 + 1 + 1，而实际上最优解是5 + 5 + 5。

算法设计贪心算法的思想与实现算法是计算机科学领域中的核心概念，它指导着解决问题的方法和步骤。

贪心算法是一种常用的算法设计思想，它在求解最优化问题时，每一步都采取当前状态下最优的选择，希望得到全局最优解。

本文将介绍贪心算法的思想和实现方式，并通过一个实际问题的案例来说明其应用。

一、贪心算法的思想贪心算法是一种贪心思想的应用，即每一步都做出在当前看来最好的选择。

它不关心整体的结果，只关心当下最优解。

贪心算法通常可以通过以下三个步骤实现：1. 贪心选择策略：在每一步中，通过一定的策略选择当前看来最优的解。

2. 确定限制条件：确定所得到的选择是否满足问题的限制条件。

3. 最优子结构：通过贪心选择策略，将原问题分解为若干子问题，每个子问题都具有最优子结构。

贪心算法的核心思想在于每一步都是局部最优解，通过一系列局部最优解，最终得到全局最优解。

然而，贪心算法并不能保证得到全局最优解，只适用于满足贪心选择策略、具有最优子结构和无后效性的问题。

二、贪心算法的实现贪心算法的实现通常分为以下几个步骤：1. 建立数学模型：通过数学表达式对问题进行建模。

2. 确定贪心选择策略：根据问题的特点和要求，确定一种贪心选择策略。

3. 构造贪心算法：根据贪心选择策略，构造出一个贪心算法来求解问题。

4. 证明算法的正确性：通过数学证明等方式，证明贪心算法得到的解是问题的最优解。

三、贪心算法的应用贪心算法可以应用于众多实际问题的求解，例如最小生成树、最短路径、背包问题等。

下面以活动选择问题为例来说明贪心算法的应用。

假设有n个活动，每个活动都有一个开始时间和结束时间。

要求从这些活动中选择出最多的互不冲突的活动（即活动之间不能出现时间上的重叠），请设计一个贪心算法来解决该问题。

算法步骤：1. 将活动按照结束时间的先后顺序进行排序。

2. 选择第一个活动作为已安排的活动。

3. 从剩余的活动中选择结束时间与已安排活动的开始时间不重叠的活动，将其加入到已安排的活动中。

贪心算法实验报告课程数据结构与算法实验名称贪心策略第页班级学号姓名实验日期：2019年9月15日报告退发(订正、重做)一、实验目的掌握贪心策略的原理和应用。

二、实验环境1、微型计算机一台2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容必做题：1、编写程序，求解普通背包问题，要求输出背包所能容纳物品的最大价值(最优值)，及与该最大价值相应的装入背包中的每件物品信息。

2、设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。

如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。

若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。

也就是说，当si≥fj或sj≥fi时，活动i与活动j 相容。

编写程序，在所给的活动集合中选出最大的相容活动子集合。

要求输出活动数量(即最优值)和最大相容活动子集中的每个活动(即最优解)。

四、实验步骤和结果(附上代码和程序运行结果截图)1、普通背包问题//goods.classpublic class goods implements Comparable<goods> {private static int ids=1;private int id;private int weight;private int value;private int use;//初始化对象//public goods(int w,int v){super();id=ids++;weight=w;value=v;use=0;}//获取输出值//public float getVW(){return this.value/this.weight;}public int getw(){return this.weight;}public int getv(){return this.value;}public int getuse(){return e;}//输出设置//public void setuse(int u){e=u;}//方法//public int compareTo(goods o){if(this.value*o.weight>o.value*this.weight) return -1;//使用交叉相乘的方法避免除法，a/b?c/d=ad?bcif(this.value*o.weight<o.value*this.weight) return 1;return 0;}public String toString(){return"物品编号"+this.id+" 物品重量"+this.weight+" 物品价值"+this.value+" 物品使用情况"+e;}}//NormalBagimport java.util.ArrayList;import java.util.PriorityQueue;public class NormalBag {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stub//初始化队列//PriorityQueue<goods> pq=initpq();//定义暂存结果数组//ArrayList<goods> place=new ArrayList<goods>();//初始化背包值//int c=10;//背包当前容量int v=0;//背包当前价值//开始放入物品//goods t;//设定暂存记录变脸while(true){//设定借宿条件//if(c==0)break;if(pq.isEmpty())break;//取出替换元素//t=pq.poll();//开始比较//if(t.getw()<=c){v+=t.getv();t.setuse(t.getw());c-=t.getw();}else{v+=c*t.getVW();t.setuse(c);c=0;}place.add(t);}//输出结果//System.out.println(v);System.out.println(place);}//创建队列元素private static PriorityQueue<goods> initpq() {// TODO Auto-generated method stubPriorityQueue<goods>pq=new PriorityQueue<goods>();pq.offer(new goods(2,6));pq.offer(new goods(2,3));pq.offer(new goods(6,5));pq.offer(new goods(5,4));pq.offer(new goods(4,6));return pq;}}2.活动安排问题public class GreedySelector {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stub//初始化//int s[]={1,3,0,5,3,5,6,8,8,2,12};//开始时间数组，已排序int f[]={4,5,6,7,8,9,10,11,12,13,14};//结束时间数组，已排序int a[]=new int[s.length];//定义标记选择过的活动数组int count=0;//活动数量计数器//开始选择//greedyselector(s,f,a);//输出//for(int i=0;i<s.length;i++){//输出活动序号if(a[i]==1){System.out.print("活动"+(i+1)+" ");count++;}}System.out.println();System.out.print("活动总数量为："+count);//输出总活动数量}private static void greedyselector(int[] s, int[] f, int[] a) { // TODO Auto-generated method stub//贪心选择为，先结束的互动优先，这样剩余的时间达到最大，安排活动最多//int n=s.length-1;a[0]=1;//最先的那个最优int j=0;for(int i=1;i<=n;i++){if(s[i]>=f[j]){a[i]=1;j=i;}elsea[i]=0;}}}五、实验总结(本次实验完成的情况，心得体会)。

贪心算法程序设计实验目的：掌握贪心算法。

实验内容：设n是一个正整数。

现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。

对于给定的正整数n，编程计算最优分解方案。

实验要求：利用贪心算法思想写出算法的伪代码和C程序代码。

(一)算法思想1）把一个正整数从中间分开（如果是偶数，直接除以2；如果是奇数，分别加1除以2，减1除以2）2）其中一部分保留在A[]数组中（奇数的话，比较大的那一部分保留给A[]数组），另一部分赋给temp，并重复1，2 步骤3）最后把temp赋给A[]数组(二)程序代码//贪心算法import java.io.*;public class Testsuanfa {public int N = this.GetN();public int[] A = new int[100];// 取得用户需要实现算法的一个正整数public int GetN() {int dvalue = 0;String value;System.out.println("请输入一个正整数： ");BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));try {value = bfr.readLine();dvalue = Integer.parseInt(value);//如果输入的不是数字，系统自动退出，并提示：“输入正确的数值！”。

} catch (IOException e) {System.out.println("输入出错了，请重新输入：");System.exit(0);} catch (NumberFormatException e2) {System.out.println("请输入正确的数字！！");System.exit(0);}return dvalue;}public void f() {int count = 0;int sum = 0;// 将这个数分解：从2到i（直到这些数的和sum大于N）for (int i = 0; sum < N; i++) {sum = 2 + i + sum;A[i] = 2 + i;count++;}// 如果sum比N大1，即把2去掉，其他数在数组的位置往前移，最后一个数加1。

#include<iostream>using namespace std;#define SIZE 11 //控制活动总数量的大小typedef int Type;void GreedySelector(int n,Type s[],Type f[],bool A[]) {A[0]=true;int j=0;for(int i=1;i<n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}else A[i]=false;}}void main(){int t=0;Type s[SIZE];Type f[SIZE];cout<<"请输入开始时间："<<endl;for(int z=0;z<SIZE;z++)cin>>s[z];cout<<"请输入结束时间："<<endl;for(int j=0;j<SIZE;j++)cin>>f[j];bool re[SIZE];GreedySelector(SIZE,s,f,re);//cout<<endl<<"可安排的活动区间为:"<<endl;for(int i=0;i<SIZE;i++){if(re[i]){// cout<<(i+1)<<" ";cout<<"可安排开始时间为："<<s[i]<<" 结束时间为："<<f[i] <<" 的活动"<<endl;t++;}}//cout<<"；"<<"活动";cout<<endl;cout<<"总共可以安排"<<t<<"个活动。

java贪心算法思路一、什么是贪心算法？贪心算法是一种基于贪心思想的算法，它在每个阶段选择局部最优解，最终得到全局最优解。

在实际应用中，贪心算法通常被用来解决一些最优化问题，如最小生成树、背包问题等。

二、Java贪心算法的实现步骤1. 确定问题的阶段：将问题分成若干个阶段。

2. 确定每个阶段的状态：定义每个阶段可能存在的状态集合。

3. 确定状态转移方程：确定从一个状态到下一个状态的转移方式。

4. 确定边界条件：确定第一个状态和最后一个状态的值。

5. 选择局部最优解：在每个阶段选择局部最优解，并将其作为当前的解。

6. 将局部最优解合并成全局最优解：将每个阶段选择的局部最优解合并成全局最优解。

三、Java贪心算法示例以背包问题为例，假设有一个容量为C的背包和n个物品，其中第i个物品重量为wi，价值为vi。

要求在不超过背包容量C的情况下，选出若干件物品使得它们的总价值最大。

该问题可以用贪心算法来解决，具体步骤如下：1. 将所有物品按照单位重量的价值从大到小排序。

2. 依次将排好序的物品放入背包中，直到放不下为止。

3. 如果某个物品无法完整放入背包中，则将它分成若干部分，将部分放入背包中，直到背包装满为止。

4. 计算所选物品的总价值，得到最终结果。

Java代码示例：```public class Knapsack {public static void main(String[] args) {int capacity = 50; // 背包容量int[] weight = {10, 20, 30}; // 物品重量int[] value = {60, 100, 120}; // 物品价值double maxValue = knapsack(capacity, weight, value);System.out.println("The maximum value is " + maxValue); }public static double knapsack(int capacity, int[] weight, int[] value) {int n = weight.length;double maxValue = 0; // 最大价值double[] ratio = new double[n]; // 单位重量的价值for (int i = 0; i < n; i++) {ratio[i] = (double) value[i] / weight[i];}// 将物品按照单位重量的价值从大到小排序for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (ratio[i] < ratio[j]) {double temp = ratio[i];ratio[i] = ratio[j];ratio[j] = temp;int tempWeight = weight[i];weight[i] = weight[j];weight[j] = tempWeight;int tempValue = value[i];value[i] = value[j];value[j] = tempValue;}}}// 依次将物品放入背包中，直到放不下为止 for (int i = 0; i < n && capacity > 0; i++) { if (weight[i] <= capacity) {maxValue += value[i];capacity -= weight[i];} else {maxValue += ratio[i] * capacity;capacity = 0;}}return maxValue;}}```四、Java贪心算法的优缺点优点：1. 算法简单，易于实现。

实验报告7课程数据结构与算法实验名称贪心策略第页班级11计本学号105032011130 姓名风律澈实验日期：2013年4月15日报告退发(订正、重做)一、实验目的掌握贪心策略的原理和应用。

二、实验环境1、微型计算机一台2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容必做题：1、编写程序，求解普通背包问题，要求输出背包所能容纳物品的最大价值(最优值)，及与该最大价值相应的装入背包中的每件物品信息。

2、设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。

如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。

若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。

也就是说，当si≥fj或sj≥fi时，活动i与活动j 相容。

编写程序，在所给的活动集合中选出最大的相容活动子集合。

要求输出活动数量(即最优值)和最大相容活动子集中的每个活动(即最优解)。

四、实验步骤和结果(附上代码和程序运行结果截图)1、普通背包问题//goods.classpublic class goods implements Comparable<goods> {private static int ids=1;private int id;private int weight;private int value;private int use;//初始化对象//public goods(int w,int v){super();id=ids++;weight=w;value=v;use=0;}//获取输出值//public float getVW(){return this.value/this.weight;}public int getw(){return this.weight;}public int getv(){return this.value;}public int getuse(){return e;}//输出设置//public void setuse(int u){e=u;}//方法//public int compareTo(goods o){if(this.value*o.weight>o.value*this.weight) return-1;//使用交叉相乘的方法避免除法，a/b?c/d=ad?bcif(this.value*o.weight<o.value*this.weight) return 1;return 0;}public String toString(){return"物品编号"+this.id+" 物品重量"+this.weight+" 物品价值"+this.value+" 物品使用情况"+e;}}//NormalBagimport java.util.ArrayList;import java.util.PriorityQueue;public class NormalBag {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stub//初始化队列//PriorityQueue<goods> pq=initpq();//定义暂存结果数组//ArrayList<goods> place=new ArrayList<goods>();//初始化背包值//int c=10;//背包当前容量int v=0;//背包当前价值//开始放入物品//goods t;//设定暂存记录变脸while(true){//设定借宿条件//if(c==0)break;if(pq.isEmpty())break;//取出替换元素//t=pq.poll();//开始比较//if(t.getw()<=c){v+=t.getv();t.setuse(t.getw());c-=t.getw();}else{v+=c*t.getVW();t.setuse(c);c=0;}place.add(t);}//输出结果//System.out.println(v);System.out.println(place);}//创建队列元素private static PriorityQueue<goods> initpq() {// TODO Auto-generated method stubPriorityQueue<goods>pq=new PriorityQueue<goods>();pq.offer(new goods(2,6));pq.offer(new goods(2,3));pq.offer(new goods(6,5));pq.offer(new goods(5,4));pq.offer(new goods(4,6));return pq;}}2.活动安排问题public class GreedySelector {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stub//初始化//int s[]={1,3,0,5,3,5,6,8,8,2,12};//开始时间数组，已排序int f[]={4,5,6,7,8,9,10,11,12,13,14};//结束时间数组，已排序int a[]=new int[s.length];//定义标记选择过的活动数组int count=0;//活动数量计数器//开始选择//greedyselector(s,f,a);//输出//for(int i=0;i<s.length;i++){//输出活动序号if(a[i]==1){System.out.print("活动"+(i+1)+" ");count++;}}System.out.println();System.out.print("活动总数量为："+count);//输出总活动数量}private static void greedyselector(int[] s, int[] f, int[] a) { // TODO Auto-generated method stub//贪心选择为，先结束的互动优先，这样剩余的时间达到最大，安排活动最多//int n=s.length-1;a[0]=1;//最先的那个最优int j=0;for(int i=1;i<=n;i++){if(s[i]>=f[j]){a[i]=1;j=i;}elsea[i]=0;}}}五、实验总结(本次实验完成的情况，心得体会)。

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
算法设计与分析
实验报告
实验二：贪心算法
【实验目的】
深入理解贪心法的算法思想，应用贪心算法解决实际的算法问题。

【实验性质】
验证性实验。

【实验要求】
有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

求解安排尽量多项活动在该场地进行，即求A的最大相容子集。

设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：
将此表数据作为实现该算法的测试数据。

【算法思想及处理过程】
【程序代码】
【实验总结】。

import java.awt.FileDialog;import java.io.*;import java.util.ArrayList;import java.util.List;import javax.swing.JFrame;public class GreedySelectorTest{boolean[] A;int[] S,F; //活动的开始时间结束时间String[] name; //活动名称public void initData(){JFrame f=new JFrame();FileDialog fileDialog=new FileDialog(f);fileDialog.setMode(0);fileDialog.setTitle("打开文件");fileDialog.setVisible(true);List list=new ArrayList();try{File file=new File(fileDialog.getDirectory()+fileDialog.getFile()); BufferedReader in=new BufferedReader(new InputStreamReader(new FileInputStream(file)));String s;while((s=in.readLine())!=null){if(s.length()>1)list.add(s);}in.close();}catch(Exception e){}f.dispose();//排序list=this.sortList(list);//初始化name=new String[list.size()+1];A=new boolean[list.size()+1];S=new int[list.size()+1];F=new int[list.size()+1];String[] s;for(int i=1;i<=list.size();i++){s=list.get(i-1).toString().split(",");name[i]=s[0].trim();S[i]=Integer.parseInt(s[1].trim());F[i]=Integer.parseInt(s[2].trim());}}public void greedySelector(int n){A[1]=true;int j=1;for(int i=2;i<=n;i++){if(S[i]>=F[j]){A[i]=true;j=i;}elseA[i]=false;}}public void showResult(){this.greedySelector(A.length-1);System.out.println("活动安排时间如下：");System.out.println("名称开始时间结束时间");for(int i=1;i<A.length;i++){if(A[i]==true)System.out.println(name[i]+" "+S[i]+" "+F[i]);}}/*** 冒泡排序* @param list* @return*/public List sortList(List list){String[] s;Object ss;int temp,temp1;for(int i=0;i<list.size();i++){for(int j=0;j<list.size()-i-1;j++){s=list.get(j).toString().split(",");temp=Integer.parseInt(s[2].trim());s=list.get(j+1).toString().split(",");temp1=Integer.parseInt(s[2].trim());if(temp>temp1){ss=list.get(j);list.set(j, list.get(j+1));list.set(j+1, ss);}}}return list;}public static void main(String args[]){GreedySelectorTest test=new GreedySelectorTest();test.initData();test.showResult();}}。

贪心算法java代码贪心算法Java代码贪心算法是一种高效的算法，它通过每次选择当前状态下最优解来得到全局最优解。

在贪心算法中，每个步骤都选择局部最优解，最终得到全局最优解。

贪心算法的应用非常广泛，比如最小生成树、最短路径、背包问题等。

下面我们以贪心算法解决最小生成树问题为例，给出Java代码实现。

最小生成树问题是指在一个带权无向图中，找到一棵树，使得这棵树包含了图中所有节点，且树的边的权值之和最小。

在贪心算法中，每次选择当前状态下最优解，因此我们可以从一个节点开始，不断添加与之相邻的边，直到所有节点都被包含在树中。

Java代码实现如下：```import java.util.*;class Edge implements Comparable<Edge>{int u;int v;int weight;public Edge(int u, int v, int weight){this.u = u;this.v = v;this.weight = weight;}public int compareTo(Edge e){return this.weight - e.weight;}}public class Prim {static int INF = Integer.MAX_VALUE;public static int prim(int[][] graph){int n = graph.length;boolean[] visited = new boolean[n];int[] dist = new int[n];Arrays.fill(dist, INF);PriorityQueue<Edge> pq = new PriorityQueue<>(); pq.offer(new Edge(0, 0, 0));int ans = 0;while(!pq.isEmpty()){Edge cur = pq.poll();if(visited[cur.v]) continue;visited[cur.v] = true;ans += cur.weight;for(int i = 0; i < n; i++){if(!visited[i] && graph[cur.v][i] < dist[i]){ dist[i] = graph[cur.v][i];pq.offer(new Edge(cur.v, i, dist[i]));}}}return ans;}public static void main(String[] args){int[][] graph = {{0, 1, 2, 3},{1, 0, 4, 5},{2, 4, 0, 6},{3, 5, 6, 0}};System.out.println(prim(graph));}}```在上面的代码中，我们定义了一个Edge类来表示边，包含起点、终点和边权值三个属性。