C++算法-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语言中，贪心算法是一种常用的优化方法，可以应用于各种问题领域，如资源分配、背包问题、图着色等。

二、基本概念贪心算法的基本思想是，在每一步选择中，总是做出在当前看来最好的选择，期望最终能得到最优解。

贪心算法并不保证得到最优解，但在很多情况下能得到满意的结果。

在C语言中，可以使用结构体、数组等数据结构来实现贪心算法。

三、应用示例以下是一个简单的贪心算法示例，用于解决公交线路规划问题。

假设有n个公交站点，我们希望通过贪心算法来规划一条公交线路，使得线路长度最短。

```c#include<stdio.h>#include<stdlib.h>typedefstruct{intstart;//起点站编号intend;//终点站编号intdistance;//站点之间的距离}Station;//贪心算法选择站点intgreedy_route(Station*stations,intn){inti,j;intbest_distance=stations[0].distance;//初始化起点站到终点的距离为最小距离intbest_route=stations[0].start;//初始化最佳路线为起点站for(i=1;i<n;i++){//考虑所有可能的路线组合，找出当前距离最短的路线和最近的站点作为下一个站点for(j=0;j<i;j++){if(stations[j].distance+stations[i].distance<best_distance){best_distance=stations[j].distance+stations[i].distance;best_route=stations[i].end;//更新最佳路线为最近的站点}}//将当前站点加入路线中stations[i].start=best_route;//将终点站编号赋值给当前站点起始站编号}returnbest_route;//返回最终的公交线路编号}```四、总结通过以上示例，我们可以看到贪心算法在公交线路规划问题中的应用。

多机调度问题贪心算法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>```定义了最大作业数和最大机器数，并引入了标准输入输出库和标准库。

供应链管理中配送路线规划算法的使用教程随着电子商务的兴起和物流行业的快速发展，供应链管理中的配送路线规划算法变得尤为重要。

准确的配送路线规划能够提高物流效率，降低成本，为企业节约时间和资源。

本文将介绍供应链管理中常用的一些配送路线规划算法，并详细说明它们的使用教程。

一、贪心算法贪心算法是一种简单而常用的算法，它在每一步都做出当前最优的选择，但并不保证全局最优解。

在配送路线规划中，贪心算法可以按照以下步骤进行：1.确定起点和终点：首先确定货物的起点和终点，通常是仓库和客户的地址。

2.计算距离矩阵：根据起点、终点和中间所有点的地址，计算出它们之间的距离矩阵。

3.选择最近邻居：从起点开始，选择距离最近的邻居作为下一个节点，将其添加到路径中。

4.更新路径和距离：将新节点添加到路径中，更新距离矩阵，重复步骤3，直到到达终点。

5.输出最优路径：输出路径和距离，路径即为货物的配送路线。

贪心算法的优点在于简单易懂，计算速度快。

然而，它的缺点是可能陷入局部最优解，不能保证得到最优的配送路线。

二、遗传算法遗传算法是一种模拟自然界进化过程的启发式优化算法。

在配送路线规划中，遗传算法可以按照以下步骤进行：1.初始化种群：根据货物的起点和终点，随机生成初始解作为种群。

2.计算适应度：根据候选解的质量，计算每个解的适应度值，一般可以使用总路程作为适应度函数。

3.选择操作：根据适应度值，按照一定的选择策略选出优秀的个体作为父代。

4.交叉操作：通过交叉操作生成新的子代个体，将父代的染色体片段互换，并保留优秀的基因。

5.变异操作：对子代个体进行变异操作，引入新的基因，增加算法的搜索空间。

6.更新种群：将父代和子代个体结合，形成新的种群。

7.重复步骤3-6：重复执行3-6步骤，直到满足停止准则。

8.输出最优解：输出适应度最优的个体，作为货物的配送路线。

遗传算法的优点在于能够全局搜索和优化，有较高的收敛性和适应性。

然而，它的缺点是计算复杂度较高，需要耗费更多的时间和计算资源。

贪心法贪心法(Greedy Approach)又称贪婪法, 在对问题求解时，总是做出在当前看来是最好的选择，或者说是：总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

如单源最短路经问题，最小生成树问题等。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心法的设计思想当一个问题具有以下的性质时可以用贪心算法求解:每一步的局部最优解，同事也说整个问题的最优解。

如果一个问题可以用贪心算法解决，那么贪心通常是解决这个问题的最好的方法。

贪婪算法一般比其他方法例如动态规划更有效。

但是贪婪算法不能总是被应用。

例如，部分背包问题可以使用贪心解决，但是不能解决0-1背包问题。

贪婪算法有时也用用来得到一个近似优化问题。

例如，旅行商问题是一个NP难问题。

贪婪选择这个问题是选择最近的并且从当前城市每一步。

这个解决方案并不总是产生最好的最优解，但可以用来得到一个近似最优解。

让我们考虑一下任务选择的贪婪算法的问题, 作为我们的第一个例子。

问题：给出n个任务和每个任务的开始和结束时间。

找出可以完成的任务的最大数量，在同一时刻只能做一个任务。

例子:下面的6个任务：start[] = {1, 3, 0, 5, 8, 5};finish[] = {2, 4, 6, 7, 9, 9};最多可完成的任务是：{0, 1, 3, 4}贪婪的选择是总是选择下一个任务的完成时间至少在剩下的任务和开始时间大于或等于以前选择任务的完成时间。

我们可以根据他们的任务完成时间，以便我们总是认为下一个任务是最小完成时间的任务。

1)按照完成时间对任务排序2)选择第一个任务排序数组元素和打印。

3) 继续以下剩余的任务排序数组。

……a)如果这一任务的开始时间大于先前选择任务的完成时间然后选择这个任务和打印。

贪心算法最短路径问题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语言代码实现。

C语言版贪心算法背包问题#include#define N 100typedef struct bao{int num;float w;float v;};typedef struct avg{int num;float val;float w;float v;};struct bao b[N];struct avg d[N];int n;float c;void Sort(){int i,j,k;struct avg temp[N];for(i=0;i<n-1;i++)< p="">{k = i;for(j=i+1;j<n;j++)< p="">if(d[k].valif(k != i){temp[i]=d[i];d[i]=d[k];d[k]=temp[i];}}}float knapsack(){int i;float x[N],sum = 0;for(i=0;ifor(i=0;i<n;i++){< p="">if(d[i].w>c) break;x[d[i].num] = 1;sum += d[i].v;c -= d[i].w;}if(i<n){< p="">x[d[i].num] = c/d[i].w;sum += x[d[i].num] * d[i].v;}return sum;}int main(){int i,j,k;float sum;printf("请输入物品总数：");scanf("%d",&n);printf("\n请输入背包容量：");scanf("%f",&c);printf("\n请输入各物品重量及价值（格式：xx,xx）：");for(i=0;i<n;i++){< p=""> scanf("%f,%f",&b[i].w,&b[i].v); }for(i=0;i<="" p="">for(i=0;i<n;i++){< p="">d[i].val = b[i].v/b[i].w;d[i].v = b[i].v;d[i].w = b[i].w;}Sort();sum = knapsack();printf("%.2f\n",sum);}</n;i++){<></n;i++){<></n){<></n;i++){<></n;j++)<></n-1;i++)<>。

算法统宗中的所有题目算法是计算机科学中的重要领域，涉及到各种问题的解决方法和技巧。

以下是算法领域中的一些常见题目：1. 排序算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序等。

这些算法的目标是将一组数据按照特定的顺序进行排列。

2. 查找算法，如线性查找、二分查找、哈希查找等。

这些算法用于在给定的数据集中查找特定的元素。

3. 图算法，如深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（如Dijkstra算法、Floyd-Warshall算法）、最小生成树算法（如Prim算法、Kruskal算法）等。

这些算法用于解决与图相关的问题，如路径搜索、连通性判断、最优路径等。

4. 动态规划，动态规划是一种将复杂问题分解成子问题来求解的方法。

常见的动态规划问题包括背包问题、最长公共子序列问题、最大子数组和问题等。

5. 字符串处理算法，如字符串匹配算法（如KMP算法、Boyer-Moore算法）、字符串编辑距离算法（如Levenshtein距离算法）等。

这些算法用于解决与字符串相关的问题，如文本搜索、模式匹配、字符串相似度计算等。

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

常见的贪心算法问题包括零钱找零问题、背包问题等。

7. 分治算法，分治算法是一种将问题分解成多个相同或相似的子问题来求解的方法。

常见的分治算法问题包括快速排序、归并排序等。

8. 图论算法，图论算法用于解决与图相关的问题，如最短路径、最小生成树、最大流等。

常见的图论算法包括Dijkstra算法、Prim算法、Kruskal算法、Ford-Fulkerson算法等。

9. 数论算法，数论算法用于解决与数学相关的问题，如素数判断、最大公约数、最小公倍数等。

常见的数论算法包括欧几里得算法、Miller-Rabin算法等。

以上只是算法领域中的一部分常见题目，还有很多其他的算法题目和应用。

c++贪心算法经典例题摘要：一、贪心算法简介1.贪心算法的定义2.贪心算法的特点3.贪心算法适用的问题类型二、C++贪心算法经典例题1.背包问题a.0-1 背包问题b.完全背包问题c.动态背包问题2.最小生成树a.Kruskal 算法b.Prim 算法3.单源点最短路径a.Dijkstra 算法b.Floyd-Warshall 算法4.最长公共子序列a.贪心算法实现b.动态规划实现正文：一、贪心算法简介贪心算法（Greedy Algorithm）是一种求解最优解的方法。

它是在对问题求解时，总是做出在当前看来是最好的选择。

贪心算法并不追求整体最优解，只希望得到较为满意的解。

贪心算法的关键是贪心策略的选择，必须满足无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

贪心算法适用的问题类型包括背包问题、最小生成树、单源点最短路径和最长公共子序列等。

二、C++贪心算法经典例题1.背包问题背包问题（Knapsack Problem）是一种典型的贪心算法问题。

它描述的是有一个背包，有一定的容量，需要装载若干物品，每个物品有一定的价值和重量，要求在不超过背包容量的前提下，如何选择装载物品使得背包中的物品总价值最大。

背包问题可以分为0-1 背包问题、完全背包问题和动态背包问题。

2.最小生成树最小生成树（Minimum Spanning Tree，简称MST）是一种图论中的算法问题。

给定一个加权连通图，求解一个生成树，使得该生成树中所有边的权值之和最小。

最小生成树的经典算法有Kruskal 算法和Prim 算法。

3.单源点最短路径单源点最短路径（Single Source Shortest Path）问题是在一个图中，从源点出发到其他所有顶点的最短路径。

经典算法包括Dijkstra 算法和Floyd-Warshall 算法。

4.最长公共子序列最长公共子序列（Longest Common Subsequence，简称LCS）问题是求两个序列中最长的公共子序列。

对贪心算法的概述和研讨福州第一中学高一(8)班汪涛指导老师：陈颖算法总览当一个问题具有“最优子结构”时，我们可以采用动态规划法解决该问题。

但是有的时候，贪心算法可以更好的处理该类问题。

总体上看，贪心算法是一种高效的、不稳定的算法；但是它在解决问题时有很多独特的优良性质，掌握贪心算法有时可以非常迅速的获得最优解或近似最优解。

关键字：贪心算法（贪婪算法），贪心算法的应用举例，Object Pascal，快速算法，不稳定算法，信息学奥赛。

何时采用何时能，又何时应该采用贪心算法呢？一般认为，凡是经过数学归纳法证明可以采用贪心算法的情况，都应该采用它。

因为它的效率是很高的。

贪心算法的弱点在于它的不稳定性，即有时它不总能返回最优解。

那么能采用贪心算法的问题具有怎样的性质呢？（何时采用贪心算法）1、它具有和动态规划问题相似的性质，即分治法中的“最优子结构”性质，即每个子问题的最优解的集合就是整体最优解。

这是必须的性质，因为贪心算法解决的问题流程就需要依序研究每个子问题，然后综合之得出最后结果。

不能采用分治法解决的问题，是理论上是不能使用贪心算法的。

而且，必须拥有最优子结构性质，才能保证贪心算法返回最优解。

2、它必须具有一种特殊的“贪心选择性”。

这种性质类同于“最优子结构”性质，但又有一些小的差别。

我们知道，在动态规划中，每一个父问题结果的得出需要它的子问题作为条件；但是“贪心选择性”则不需要；贪心选择性所做的是一个非线性的子问题处理过程，即一个子问题并不依赖于另一个子问题，但是子问题间有严格的顺序性。

要证明一个问题具有“贪心选择性”，就必须证明每一步所做的贪心选择最终导致一个问题的整体最优解。

这也是必须的性质。

如果一个问题具有上述两个性质，理论上就应该采用贪心算法。

处理流程经由贪心算法处理的问题需要经过排序。

即把“最贪心”的子结果排在序列的最前面，一直到“最不贪心的”。

这是处理问题的第一步。

然后依序解决问题而得出最终结果。

贪⼼算法总结简介贪⼼算法（英⽂：greedy algorithm），是⽤计算机来模拟⼀个“贪⼼”的⼈做出决策的过程。

这个⼈⼗分贪婪，每⼀步⾏动总是按某种指标选取最优的操作。

⽽且他⽬光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想⽽知，并不是所有的时候贪⼼法都能获得最优解，所以⼀般使⽤贪⼼法的时候，都要确保⾃⼰能证明其正确性。

本⽂主要介绍，在解决诸多贪⼼算法的问题之后的⼼得。

常⽤场景最常见的贪⼼算法分为两种。

「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从⼩到⼤）选择。

」。

「我们每次都取 XXX 中最⼤/⼩的东西，并更新 XXX。

」（有时「XXX 中最⼤/⼩的东西」可以优化，⽐如⽤优先队列维护）第⼀种是离线的，先处理后选择，第⼆种是在线的，边处理边选择。

常见的出题背景为:确定某种最优组合（硬币问题）区间问题（合理安排区间）字典序问题最值问题A最优组合硬币问题是贪⼼算法⾮常经典的题⽬，关于最优组合问题，我认为主要分为两种类型:简单 -- 直接排序之后按照某种策略选取即可复杂 -- 除了按照贪⼼策略外，还需要进⾏某些处理或者模拟硬币问题硬币问题有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。

现在要⽤这些硬币来⽀付A元，最少需要多少枚硬币？假设本题⾄少存在⼀种⽀付⽅法。

0≤C1、C5、C10、C50、C100、C500≤1090≤A≤109本题是上述说的简单类型的题⽬，简⽽⾔之要使得硬币最少，则优先使⽤⼤⾯额的硬币。

因此本题的解法便⾮常清晰了，只需要从后往前遍历⼀遍即可（默认为硬币已经按⾯额⼤⼩进⾏排序）const int V[6] = {1, 5, 10, 50, 100, 500};int A, C[6]; // inputvoid solve(){int ans(0);for (int i = 5; i >= 0; -- i){int t = min(A / V[i], C[i]);A -= t * V[i];ans += t;}cout << ans << '\n';}零花钱问题POJ3040 AllowanceDescriptionAs a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like topay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.Input* Line 1: Two space-separated integers: N and C* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.Output* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowanceSample Input3 610 11 1005 120Sample Output111这题的题⽬⼤意是:农场主每天都要给贝西⾄少为C的津贴。

贪心算法哈夫曼编码c语言哈夫曼编码的贪心算法可以分为以下几步：1. 读入需要编码的字符及其出现频率，并按照频率从小到大排序。

2. 构建哈夫曼树。

首先将所有字符看成只有一个节点的树，然后取出频率最小的两棵树，将它们合并成一棵树，这棵树的频率是两棵树的频率之和。

继续取出频率最小的两棵树，重复上述过程，直到只剩下一棵树为止，这就是哈夫曼树。

3. 对哈夫曼树进行编码。

从哈夫曼树的根节点开始，往左走为0，往右走为1，一直走到叶子节点，记录下这个叶子节点代表的字符的编码。

这就是哈夫曼编码。

以下是用C语言实现的贪心算法实现：```c#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_N 256 // 假设字符集大小为256typedef struct node {char ch; // 字符int freq; // 频率struct node *left, *right; // 左右子节点} Node;// 建立一个新的节点Node* new_node(char ch, int freq) {Node *node = (Node*)malloc(sizeof(Node));node->ch = ch;node->freq = freq;node->left = node->right = NULL;return node;}// 在nodes数组中找寻最小的两个节点void find_min_two_nodes(Node **nodes, int size, int *min1, int *min2) {*min1 = *min2 = -1;for (int i = 0; i < size; i++) {if (nodes[i] == NULL) continue;if (*min1 == -1 || nodes[i]->freq < nodes[*min1]->freq) {*min2 = *min1;*min1 = i;} else if (*min2 == -1 || nodes[i]->freq < nodes[*min2]->freq) {*min2 = i;}}}// 构建哈夫曼树Node* build_huffman_tree(char *str, int *freq, int n) {Node *nodes[MAX_N];for (int i = 0; i < n; i++) {nodes[i] = new_node(str[i], freq[i]);}int size = n;while (size > 1) {int min1, min2;find_min_two_nodes(nodes, size, &min1, &min2);Node *node = new_node(0, nodes[min1]->freq +nodes[min2]->freq);node->left = nodes[min1];node->right = nodes[min2];nodes[min1] = node;nodes[min2] = NULL;size--;}return nodes[0];}// 递归生成哈夫曼编码void gen_huffman_code(Node *root, char *code, int depth, char **table) {if (root == NULL) return;if (root->left == NULL && root->right == NULL) {code[depth] = '\0';table[root->ch] = (char*)malloc((depth + 1) * sizeof(char)); strcpy(table[root->ch], code);return;}code[depth] = '0';gen_huffman_code(root->left, code, depth + 1, table);code[depth] = '1';gen_huffman_code(root->right, code, depth + 1, table); }// 哈夫曼编码char** huffman_code(char *str, int *freq, int n) {Node *root = build_huffman_tree(str, freq, n);char **table = (char**)malloc(MAX_N * sizeof(char*)); char code[MAX_N];gen_huffman_code(root, code, 0, table);return table;}int main() {char str[] = "ABACCABB";int freq[] = {2, 3, 1, 2, 1, 1, 1, 1};int n = strlen(str);char **table = huffman_code(str, freq, n);for (int i = 0; i < n; i++) {printf("char: %c, code: %s\n", str[i], table[str[i]]);}return 0;}```输出结果：```char: A, code: 11char: B, code: 0char: A, code: 11char: C, code: 100char: C, code: 100char: A, code: 11char: B, code: 1char: B, code: 01```这就是对字符串"ABACCABB"进行哈夫曼编码的结果。

课程设计--贪心算法数据结构课程设计贪心算法专业软件工程班级B软件121 学号1210701132 学生姓名目录1设计题目 (1)2设计分析 (1)3设计实现 (4)4测试方法 (7)4.1测试目的 (7)4.2 测试输入 (7)4.3 正确输出 (7)4.4 实际输出 (8)5分析与探讨 (8)5.1 测试结果分析 (8)5.2 探讨与改进 (8)6设计小结 (8)1 设计题目有n项任务，要求按顺序执行，并设定第i项任务需要t[i]单位时间。

如果任务完成的顺序为1，2，…，n，那么第i项任务完成的时间为c[i]=t[1]+…+t[i]，平均完成时间（Average Completion Time，ACT）即为（c[1]+…+c[n]）/n。

本题要求找到最小的任务平均时间。

输入要求：输入数据中包含几个测试案例。

每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个非负整数t（t<=1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。

输出要求：对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。

每个案例对应的输出结果都占一行。

若输入某一个案例中任务数目n=0，则对应输出一个空行。

输入例子：44 2 8 1-1表示有四个任务，各自完成需要的时间单位分别是4，2，8，1，第三行输入-1表示结束。

输出例子：要求程序运行后的输出结果为：6.50。

2 设计分析算法是为了求解一个问题需要遵循的，被青春地指定的简单指令的集合。

任何程序基本上都是要用特点的算法来实现的。

算法性能的好坏，直接决定了所实现程序性能的优劣。

贪心算法通过一系列的选择来的得到一个问题的解。

它所做的每一个选择都是当前的状态下某种意义的最好选择，即贪心选择。

希望通过每次所做的贪心选择导致最终结果问题的一个最优解。

这种启发式的策略并不总能奏效，然而在许多情况下能达到预期的目的。

这个题目属于贪心算法应用中的任务调度问题。

C语⾔基于贪⼼算法解决装箱问题的⽅法本⽂实例讲述了C语⾔基于贪⼼算法解决装箱问题的⽅法。

分享给⼤家供⼤家参考，具体如下：问题描述：有⼀些箱⼦，容量为V，同时有n个物品，每个物品有⼀个体积（⼩于等于箱⼦容量），要求将物品全部装⼊箱⼦中，使占⽤的箱⼦数尽量少。

贪⼼算法中要求每⼀步的解都是当前步骤中的最优解。

原问题的解可以通过⼀系列局部最优的选择来达到，这种选择并不依赖于⼦问题的解。

算法思想：1、数据结构要求求解箱⼦数⽬，也就是说不能确定会占⽤多少个箱⼦，因此采⽤链表的形式来存储箱⼦及其信息。

同时，每个箱⼦中物品的数⽬也⽆法确定，同理采⽤链表来存储每个箱⼦中的物品信息。

由此得出数据节点的定义：typedef struct{int gno;int gv;}Goods;typedef struct node{int gno;struct node *link;}GNode;typedef struct node1{int remainder;GNode * head;struct node1 * next;}GBox;2、求解思路使打开的箱⼦数尽量少，也就是说每个箱⼦容积被尽可能多地占⽤。

将物品按照体积降序排列后，再从第⼀个物品开始，挨个寻找能放下它的箱⼦，这样可以保证局部最优。

void GoodsSort(Goods goods[], int n){int i, j;Goods t;for (i = 0; i<n - 1; i++){for (j = i + 1; j<n; j++){if (goods[i].gv<goods[j].gv){t = goods[i];goods[i] = goods[j];goods[j] = t;}}}for (i = 0; i<n; i++)printf("%d %d\n", goods[i].gno, goods[i].gv);排序完成，就可以正式开始装箱⼦了。

CC++贪⼼算法解决TSP问题贪⼼算法解决旅⾏商问题TSP问题（Traveling Salesman Problem，旅⾏商问题），由威廉哈密顿爵⼠和英国数学家克克曼T.P.Kirkman于19世纪初提出。

问题描述如下：有若⼲个城市，任何两个城市之间的距离都是确定的，现要求⼀旅⾏商从某城市出发必须经过每⼀个城市且只在⼀个城市逗留⼀次，最后回到出发的城市，问如何事先确定⼀条最短的线路已保证其旅⾏的费⽤最少？下⾯采⽤贪⼼算法来解决旅⾏商问题。

贪⼼算法：⼜称贪婪算法（greedy algorithm）,该算法是指：在对问题求解时，总是做出当前情况下的最好选择，否则将来可能会后悔，故名“贪⼼”。

这是⼀种算法策略，每次选择得到的都是局部最优解。

选择的策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

针对TSP问题，使⽤贪⼼算法的求解的过程为：1.从某⼀个城市开始，每次选择⼀个城市，直到所有的城市被⾛完。

2.每次在选择下⼀个城市的时候，只考虑当前情况，保证迄今为⽌经过的路径总距离最⼩。

具体实现：C++：#include<iostream>using namespace std;int main(){int i,j,k,l;int n;cin>>n;//初始化城市个数int S[n];//⽤于存储已访问过的城市int D[n][n];//⽤于存储两个城市之间的距离int sum = 0;//⽤于记算已访问过的城市的最⼩路径长度int Dtemp;//保证Dtemp⽐任意两个城市之间的距离都⼤（其实在算法描述中更准确的应为⽆穷⼤）int flag;////最为访问的标志，若被访问过则为1，从未被访问过则为0//下⾯初始化城市之间的距离for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>D[i][j];//初始化城市之间的距离，由⾃⼰输⼊，应注意i==j时D[i][j]=0，且D[i][j]==D[j][i];}}i = 1;//i是⾄今已访问过的城市S[0] = 0;do{k = 1;Dtemp = 10000;do{l = 0;flag = 0;do{if(S[l] == k){//判断该城市是否已被访问过，若被访问过，flag = 1;//则flag为1break;//跳出循环，不参与距离的⽐较}elsel++;}while(l < i);if(flag == 0&&D[k][S[i - 1]] < Dtemp){//D[k][S[i - 1]]表⽰当前未被访问的城市k与上⼀个已访问过的城市i-1之间的距离*/j = k;//j⽤于存储已访问过的城市kDtemp = D[k][S[i - 1]];//Dtemp⽤于暂时存储当前最⼩路径的值}k++;}while(k < n);S[i] = j;//将已访问过的城市j存⼊到S[i]中i++;sum += Dtemp;//求出各城市之间的最短距离，注意：在结束循环时，该旅⾏商尚未回到原出发的城市 }while(i < n);sum += D[0][j];//D[0][j]为旅⾏商所在的最后⼀个城市与原出发的城市之间的距离for(j = 0; j < n; j++){//输出经过的城市的路径cout<<j<<"-->";}cout<<endl;cout<<sum<<endl;//输出最短路径的值return 0;}。