贪心算法多机调度问题c程序

//多机调度问题/*贪心法求解多级调度问题的贪心策略师最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样就可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的时间。

按照最长处理时间作业优先的贪心测落，当m>n,时，只要将机器ide [0,ti)时间去见分配给作业j即可，当m<n时，首先将n个作业从大到小排序，然后依次顺序将作业分配给空闲的处理机算法伪代码将数组t[n]从大到小排序，对应的作业序号存储在数组p[n]中；将数组d[m]初始化为零3：for（i0;i<=m;i++)3.1:s[i]={p[i]}:将m个作业分配给m个机器3.2 d[i]=t[i];for(i=m+1;i<=n;i++)4.1 j=数组d[m]中最小值对应的下标；//j为最先空闲的机器序号4.2 s[j]=s[j]+{p[i]};//将作业分配给最先空闲的的机器j4.3 d[j]=d[j]+d[t];//机器j将在d[j]后空闲*/#include<iostream>using namespace std;void lowsort(int *t,int *p,int n)//将数组t[n]按从小到大的顺序排序，相应的任务编号数组p[n]也要随之改变{int index;for(int i=0;i<n;i++){index=i;for(int j=i+1;j<n;j++){if(t[index]<t[j])index=j;}if(index!=i){int temp;temp=t[index];t[index]=t[i];t[i]=temp;temp=p[i];p[i]=p[index];p[index]=temp;}}int find(int *d,int m){int min=d[0];int k;for(int i=0;i<m;i++){if(d[i]<min){min=d[i];k=i;}}return k;}void ajust(int *t,int *d,int *p,int *s,int n,int m){lowsort(t,p,n);for(int i=0;i<m;i++){d[m]=0;}for(i=0;i<m;i++){s[i]=p[i];cout<<"机器"<<i+1<<"做了任务"<<p[i]<<endl;d[i]=t[i];}for(i=m;i<n;i++){int j=find(d,m);//查找数组d[m]中最小值对应的下标s[j]=s[j]+p[i];cout<<"机器"<<j+1<<"做了任务"<<p[i]<<endl;d[j]=d[j]+t[i];}}void main()int n,m;cout<<"输入任务数量"<<endl;cin>>n;cout<<"输入机器个数"<<endl;cin>>m;int *t=new int [n];int *s=new int [n];int *d=new int [m];int *p=new int[n];cout<<"输入任务编号"<<endl;for(int k=0;k<n;k++)cin>>p[k];cout<<"每件任务所花费的时间"<<endl;for(int i=0;i<n;i++)cin>>t[i];ajust(t,d,p,s,n,m);}。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

贪心算法几个经典例子c语言1. 零钱兑换问题题目描述：给定一些面额不同的硬币和一个总金额，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

如果没有任何一种硬币组合能够凑出总金额，返回 -1。

贪心策略：每次选择面额最大的硬币，直到凑出总金额或者无法再选择硬币为止。

C语言代码：int coinChange(int* coins, int coinsSize, int amount){int count = 0;for(int i = coinsSize - 1; i >= 0; i--){while(amount >= coins[i]){amount -= coins[i];count++;}}return amount == 0 ? count : -1;}2. 活动选择问题题目描述：有 n 个活动，每个活动都有一个开始时间和结束时间，选择一些活动使得它们不冲突，且能够参加的活动数最多。

贪心策略：每次选择结束时间最早的活动，直到所有活动都被选择或者无法再选择为止。

C语言代码：typedef struct{int start;int end;}Activity;int cmp(const void* a, const void* b){return ((Activity*)a)->end - ((Activity*)b)->end;}int maxActivities(Activity* activities, int n){qsort(activities, n, sizeof(Activity), cmp);int count = 1;int end = activities[0].end;for(int i = 1; i < n; i++){if(activities[i].start >= end){count++;end = activities[i].end;}}return count;}3. 跳跃游戏题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。

多机调度问题贪心算法c语言一、引言多机调度问题是指将一组作业分配给多台机器，使得完成所有作业的时间最短。

在实际生产中，多机调度问题是一个常见的优化问题。

贪心算法是解决多机调度问题的一种有效方法。

本文将介绍贪心算法在C语言中的应用。

二、问题描述假设有n个作业需要分配给m台机器进行加工处理，每个作业需要的时间不同，每台机器的处理速度也不同。

现在需要设计一个算法，将这些作业分配给这些机器进行加工处理，并使得完成所有作业所需时间最短。

三、贪心算法思路贪心算法是一种基于局部最优解来构造全局最优解的思想。

对于多机调度问题，我们可以采用以下贪心策略：1. 将所有作业按照所需时间从大到小排序；2. 将第一个作业分配给第一台机器；3. 对于剩余的作业，选择当前处理时间最短的那台机器进行分配；4. 重复步骤3直到所有作业都被分配完毕。

四、C语言实现下面是C语言实现多机调度问题贪心算法的代码：#include <stdio.h>#include <stdlib.h>#define MAX_JOB 1000#define MAX_MACHINE 1000int cmp(const void *a, const void *b) {return *(int *)b - *(int *)a;}int main() {int n, m, job[MAX_JOB], machine[MAX_MACHINE] = {0}; scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) {scanf("%d", &job[i]);}qsort(job, n, sizeof(int), cmp);for (int i = 0; i < n; i++) {int min_time = machine[0], min_index = 0;for (int j = 1; j < m; j++) {if (machine[j] < min_time) { min_time = machine[j]; min_index = j;}}machine[min_index] += job[i]; }int max_time = machine[0];for (int i = 1; i < m; i++) {if (machine[i] > max_time) { max_time = machine[i];}}printf("%d\n", max_time);return 0;}五、代码解析1. 宏定义和头文件引入：```#define MAX_JOB 1000#define MAX_MACHINE 1000#include <stdio.h>#include <stdlib.h>```定义了最大作业数和最大机器数，并引入了标准输入输出库和标准库。

贪心算法-多机调度一、问题描述设有n个独立的作业，由m台机器进行加工处理，作业i所需的处理时间为t（i）。

约定，任何作业可以在任何机器上加工处理，但未完成前不允许中断处理。

任何作业不能拆分成更小的子作业。

多机调度问题要求给出一种作业调度方案，使n个作业在尽可能短的时间内完成。

二、算法分析1当n<=m时，将机器i的【0~t(i)】时间分配给作业i即可。

2当n>m时，首先将n个作业按照时间从大到小排列。

然后照此顺序将作业分配给空闲的处理机即可。

3创建3个类:JobNode类,MachineNode类, MinHeap类分别用于作业信息，机器信息，对机器类型的堆处理三、代码#include<iostream>using namespace std;#define Max 15template <class Type>class MinHeap{public:MinHeap(int ms);~MinHeap();void Insert(const Type& x);void DeleteMin(Type& x);protected:void FilterDown();//自顶向下构造堆void FilterUp();//自底向上构造堆private:Type *heap;int length;};////////////////////////////////////////template <class Type>MinHeap<Type>::MinHeap(int m){heap=new Type[m+1];length=0;}////////////////////////////////////////template <class Type>void MinHeap<Type>::Insert(const Type& x) {heap[++length]=x;FilterUp();}////////////////////////////////////////template <class Type> template <class Type>void MinHeap<Type>::FilterUp(){//自底向上进行调整int i=length,j=i/2;//父节点的编号Type temp=heap[i];while(i>1){if(temp>=heap[j])break;//找到了相应的位置else{heap[i]=heap[j];i=j;j=i/2;}}heap[i]=temp;}////////////////////////////////////////template <class Type>void MinHeap<Type>::DeleteMin(Type &x){x=heap[1];heap[1]=heap[length];length--;FilterDown();}////////////////////////////////////////template <class Type>void MinHeap<Type>::FilterDown(){int i=1,j=i*2;Type temp=heap[i];while(j<=length){if(j<length && heap[j]>heap[j+1])j++;//如果左右子树都存在,找出最小者,用j标记if(temp<heap[j])break;//找到了相应的位置else{heap[i]=heap[j];i=j;j=2*i;}}heap[i]=temp;}////////////////////////////////////////template <class Type>MinHeap<Type>::~MinHeap(){delete[] heap;}////////////////////////////////////////class JobNode{friend void Greedy(JobNode *,int ,int);friend void main(void);public:operator int() const {return time;}int ID,time;};class MachineNode{friend void Greedy(JobNode *,int ,int); public:operator int() const {return avail;}int ID,avail;};void Sort(JobNode a[],int n){int i,j,k;JobNode tmp;for(i=1;i<n;i++){k=i;for(j=i+1;j<=n;j++){if(a[j].time<a[k].time) k=j;}if(k!=i){tmp=a[i];a[i]=a[k];a[k]=tmp;}}}void Greedy(JobNode a[],int n,int m){if(n<=m){cout<<"为每个作业分配一台机器."<<endl;return;}Sort(a,n);MinHeap<MachineNode>H(m);MachineNode x;for(int i=1;i<=m;i++){x.avail=0;x.ID=i;H.Insert(x);}for(i=n;i>=1;i--){H.DeleteMin(x);cout<<"\n将机器"<<x.ID<<"从"<<x.avail<<"到"<<(x.avail+a[i].time)<<"的时间段分配给作业"<<a[i].ID<<endl;x.avail+=a[i].time;H.Insert(x);}}void main(){int i;int job_cnt; //作业的数目float machine_cnt;//机器数目int Time_of_all=0;JobNode a[Max];//作业所需要的时间// MachineNode b[Max];cout<<"==========多机调度问题===========\n";cout<<"输入机器个数：";cin>>machine_cnt;cout<<"输入作业个数(小于15)：";cin>>job_cnt;for(i=1;i<=job_cnt;i++){cout<<"\n请输入第"<<i<<"个作业处理时间:";cin>>a[i].time;a[i].ID=i;}Greedy(a,job_cnt,machine_cnt);}四、结果截图五．实验总结多机调度问题是生活中比较典型的例子，根据经验我们很好确定贪心算法的贪心标准，但是落实到编程，还是有点不够得心应手，还需要加强自己的编程能力。

最小生成树例题贪心算法c语言算法与设计题目：最小生成树例题——贪心算法在C语言算法与设计中的应用引言:在算法和数据结构的学习过程中，贪心算法是一种常见且重要的思想。

它通过每一步局部最优的选择来构建整体最优解。

最小生成树问题是贪心算法的经典例题之一，而在C语言算法与设计中，理解并应用贪心算法是非常必要的。

本文将围绕最小生成树例题展开，探讨贪心算法在C语言算法与设计中的应用。

一、最小生成树（Minimum Spanning Tree）的定义与理解1.1 概念解析最小生成树是图论中的一个概念，它指的是在连通图中找到一棵树，使得这棵树的所有边的权值之和最小。

最小生成树常应用于优化问题，如电缆布线以及城市间道路建设等。

1.2 算法应用最小生成树常用于解决具有边权的连通图问题。

在实际应用中，我们通常使用Kruskal算法或Prim算法来求解最小生成树。

二、Kruskal算法详解2.1 思想描述Kruskal算法是一种基于贪心思想的算法，其主要思路是依次选择边权最小且不形成回路的边，直到生成最小生成树。

2.2 具体步骤（1）将图中的所有边按照权值从小到大进行排序；（2）从权值最小的边开始，如果该边的两个端点不在同一个连通分量中，则将其加入最小生成树，并合并两个连通分量；（3）重复步骤（2），直到最小生成树包含图中的所有节点。

2.3 例子分析以以下图为例说明Kruskal算法的应用过程：```（图1）```（1）将图中的边按照权值从小到大排序得到如下顺序：```A-B: 1E-F: 1B-C: 2E-G: 2C-D: 3D-F: 3F-G: 4```（2）选取权值最小的边A-B，并将A和B加入最小生成树。

此时连通分量为{A}和{B}。

```（图2）```（3）选取权值次小的边E-F，可以将其加入最小生成树，同时连通分量中加入F。

此时连通分量为{A}，{B}和{F}。

```（图3）```（4）依次选择权值较小的边，直到最小生成树中包含图中的所有节点。

多机调度问题的贪心算法实现（使用C语言）标题：多机调度问题的贪心算法实现（使用C语言）简介：多机调度问题是一个经典的组合优化问题，旨在将一组待处理的任务分配给多台计算机，使得任务完成时间最小化。

贪心算法是一种常用的解决该问题的方法，本文将介绍如何使用C语言实现贪心算法来解决多机调度问题。

引言：随着计算机技术的不断进步，我们面临的任务越来越多，如何有效地将任务分配给多台计算机成为一个重要的问题。

多机调度问题涉及到任务的分配、计算机资源的利用率以及任务完成时间的优化。

本文将通过贪心算法来解决这一问题，贪心算法通过每次选择局部最优解，最终得到一个全局最优解。

1. 多机调度问题的贪心算法概述1.1 贪心算法的基本思想1.2 多机调度问题的贪心策略选择1.3 贪心算法实现的步骤2. 多机调度问题的输入与输出2.1 输入：任务集合和计算机集合2.2 输出：任务分配结果和任务完成时间3. 多机调度问题的贪心算法实现3.1 任务排序3.2 计算机选择3.3 任务分配3.4 计算任务完成时间4. 多机调度问题的贪心算法代码实现（使用C语言） 4.1 数据结构定义4.2 输入模块4.3 贪心算法实现函数4.4 输出模块5. 算法性能分析和改进5.1 算法的时间复杂度分析5.2 算法的空间复杂度分析5.3 改进思路：局部搜索算法的引入6. 总结与展望6.1 对多机调度问题贪心算法的观点和理解6.2 对未来算法改进的展望结论：本文详细介绍了如何使用C语言实现贪心算法来解决多机调度问题。

贪心算法通过选择局部最优解，使得任务完成时间最小化。

此外，我们还讨论了算法的性能分析和改进方向，展望了未来对算法的进一步优化。

通过本文的学习，读者能够更加全面深刻地理解多机调度问题及贪心算法的应用。

参考文献：[1] 文献1[2] 文献2[3] 文献3。

贪心算法最短路径问题c语言代码贪心算法最短路径问题C语言代码在计算机算法的领域中，贪心算法是一种常见的解决问题的方法。

贪心算法是一种寻找最优解的方法，就是在每个步骤中都采取最优的选择，这样每一步的最优解最终就可以得到整体的最优解。

在实际应用中，贪心算法通常被用于NP问题的解决，例如最短路径问题。

本文将介绍如何用C语言实现贪心算法解决最短路径问题。

1. 最短路径问题概述最短路径问题是一种图论问题，是指在一个有权重的有向图或无向图中，从一个指定的起点节点到达一个指定终点节点的最短路径问题。

在实际应用中，最短路径问题的应用非常广泛，例如地图导航、网络寻路、信息传递等等。

2. 贪心算法的原理贪心算法是一种自顶向下的设计方法，它主要依赖与一种贪心的选择方法。

在每个步骤中，都会选择能够最优化当前直接的步骤的答案。

因此，当遇到问题难以确定最优解时，可以使用贪心算法。

一般来说，贪心算法的优点是简单易懂，并且在特定情况下能够得到准确的答案。

3. C语言代码实现快速查找从起点到所有节点的距离是这个问题的关键，可以使用某种最短路算法，例如Dijkstra算法或贪心算法。

在这里，我们使用贪心算法解决最短路径问题。

以下是C语言代码示例：#include <stdio.h> #include <stdlib.h> #include <string.h>#define V 6int min_distance(int distance[], int visited[]) { int min_index, min_distance = INT_MAX;for (int i = 0; i < V; i++) { if (visited[i] == 0 && distance[i] <= min_distance){ min_distance = distance[i]; min_index = i; } }return min_index; }int dijkstra(int graph[V][V], int source, int destination) { int distance[V], visited[V], count; memset(distance, 0, sizeof(distance)); memset(visited, 0, sizeof(visited));for (int i = 0; i < V; i++){ distance[i] = INT_MAX; }distance[source] = 0;for (count = 0; count < V - 1; count++){ int u = min_distance(distance, visited);visited[u] = 1;for (int v = 0; v < V; v++){ if (!visited[v] && graph[u][v] &&distance[u] != INT_MAX && distance[u] + graph[u][v]< distance[v]) { distance[v] =distance[u] +graph[u][v]; } } }return distance[destination]; }int main() { int graph[V][V] = { { 0, 1, 0,0, 0, 0 }, { 0, 0, 9, 0, 0,0 }, { 2, 0, 0, 3, 0, 1 }, { 0, 0, 0, 0, 2, 0 }, { 4,6, 0, 2, 0, 0 }, { 0, 0, 0,0, 1, 0 } };int source = 0, destination = 5;int distance = dijkstra(graph, source,destination);printf("The shortest distance from node %dto %d is: %d\n", source, destination, distance);return 0; }4. 结尾在本文中，我们介绍了贪心算法解决最短路径问题的原理和C语言代码实现。