算法设计与实现--贪心篇

贪心算法

贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法，以期望能够通过一系列局部最优的选择达到全局最优。贪心算法的关键是定义好局部最优的选择，并且不回退，即一旦做出了选择，就不能撤销。

一般来说，贪心算法适用于满足以下两个条件的问题：

  1. 最优子结构性质（Optimal Substructure）： 问题的最优解包含了其子问题的最优解。这意味着可以通过子问题的最优解来构造原问题的最优解。
  2. 贪心选择性质（Greedy Choice Property）： 当考虑做某个选择时，贪心算法总是选择当前看起来最优的解，而不考虑其他可能性。这个选择是局部最优的，希望通过这种选择能够达到全局最优。

关键的两步
提出贪心策略：观察问题特征，构造贪心选择
证明贪心正确：假设最优方案，通过替换证明

相关问题

1、部分背包问题

问题描述

部分背包问题是背包问题的一个变体，与 0-1 背包问题和完全背包问题不同。在部分背包问题中，每个物品可以选择一部分放入背包，而不是必须选择放入或不放入。

以下是部分背包问题的算法思想：

  1. 计算单位价值： 对每个物品计算单位价值，单位价值等于物品的价值/物品的重量。

    单位价值=物品的价值/物品的重量

  2. 按单位价值降序排序： 将所有物品按照单位价值降序排列，这样就可以优先选择单位价值较高的物品。

  3. 贪心选择： 从排好序的物品列表中按顺序选择物品放入背包。对于每个物品，可以选择一部分（即部分背包），而不必全部选择。

  4. 计算总价值： 根据所选物品计算放入背包的总价值

算法实现

#include <stdio.h>
#include <stdlib.h>// 物品的结构
struct Item{int weight;  // 物品重量 int value;   // 物品价值 
}; // 1计算单位价值
double computeUnitValue(struct Item item){double result = item.value/item.weight;return result;
} // 2 按单位价值进行降序排序
// 在这个比较函数中，参数的类型为 const void*，
//这是因为这个函数是用于通用排序算法（例如 qsort）的，
//而通用排序算法不关心待排序元素的具体类型
int compare(const void* a,const void* b) {// *(struct Item*) // 这是一种类型转换，将通用指针 const void* 转换为具体类型 struct Item*double unitValueA = computeUnitValue(*(struct Item*)a);double unitValueB = computeUnitValue(*(struct Item*)b);if(unitValueA < unitValueB){return 1;}else if(unitValueA > unitValueB){return -1;}else{return 0;}
}// 3 贪心算法
double fractionalKnapsack(struct Item items[],int n,int vtl) {// 跟据单位价值降序排列 qsort(items,n,sizeof(struct Item),compare);// 最大总价值 double maxValue = 0.0;  // 从排好序的物品列表中贪心选择，选择单位价值大的物品// 此时的items 是已经是跟据单位价值降序排序的，所以items[0] 是单位价值最大的物品 for(int i=0;i<n;i++){//  如果背包的容量>=物品的容量，则贪心策略，将整个物品放入背包 if(vtl>=items[i].weight){maxValue += items[i].value;  //  最大的价值更新 vtl -= items[i].weight;		// 背包容量更新 }else{ // 如果背包容量没法将整个物品放入，则计算他的单位价值，然后单位价值*剩余背包容量 maxValue += computeUnitValue(items[i])*vtl;break;}} return maxValue;
}// 主函数
int main() {struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};int n = sizeof(items) / sizeof(items[0]);int vtl = 50; // 背包容量 double maxValue = fractionalKnapsack(items, n, capacity);printf("Maximum value that can be obtained = %.2f\n", maxValue);return 0;
}

2、哈夫曼编码

哈夫曼编码（Huffman Coding）是一种基于字符出现频率的编码方式，它通过使用较短的比特序列来表示出现频率较高的字符，从而实现对数据的高效压缩。这种编码方式是由大卫·哈夫曼（David A. Huffman）于1952年提出的。

哈夫曼编码的基本思想：

  1. 构建哈夫曼树（Huffman Tree）：
    • 对于需要编码的字符，根据其出现频率构建一个哈夫曼树。
    • 频率越高的字符在树中离根越近，频率越低的字符在树中离根越远。（首先选择最小的两个频）
  2. 分配编码：
    • 遍历哈夫曼树的路径，给每个字符分配一个独一无二的二进制编码。
    • 一般来说，向左走表示添加一个0，向右走表示添加一个1。
  3. 生成哈夫曼编码表：
    • 将每个字符与其对应的二进制编码建立映射关系，形成哈夫曼编码表。

算法实现

#include <stdio.h>
#include <stdlib.h>// 哈夫曼树节点结构
struct HuffmanNode {char data;int frequency;struct HuffmanNode* left;struct HuffmanNode* right;
};// 字符频率表结构
struct FrequencyTable {char data;int frequency;
};// 优先队列中的元素
struct PriorityQueueElement {struct HuffmanNode* node;struct PriorityQueueElement* next;
};// 优先队列结构
struct PriorityQueue {struct PriorityQueueElement* front;
};// 初始化优先队列
void initPriorityQueue(struct PriorityQueue* pq) {pq->front = NULL;
}// 插入元素到优先队列
void insertPriorityQueue(struct PriorityQueue* pq, struct HuffmanNode* node) {struct PriorityQueueElement* newElement = (struct PriorityQueueElement*)malloc(sizeof(struct PriorityQueueElement));newElement->node = node;newElement->next = NULL;if (pq->front == NULL || node->frequency < pq->front->node->frequency) {newElement->next = pq->front;pq->front = newElement;} else {struct PriorityQueueElement* current = pq->front;while (current->next != NULL && current->next->node->frequency <= node->frequency) {current = current->next;}newElement->next = current->next;current->next = newElement;}
}// 从优先队列中取出最小元素
struct HuffmanNode* extractMinPriorityQueue(struct PriorityQueue* pq) {if (pq->front == NULL) {return NULL;}struct HuffmanNode* minNode = pq->front->node;struct PriorityQueueElement* temp = pq->front;pq->front = pq->front->next;free(temp);return minNode;
}// 构建哈夫曼树
struct HuffmanNode* buildHuffmanTree(struct FrequencyTable frequencies[], int n) {struct PriorityQueue pq;initPriorityQueue(&pq);// 初始化优先队列，每个节点作为一个单独的树for (int i = 0; i < n; ++i) {struct HuffmanNode* newNode = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));newNode->data = frequencies[i].data;newNode->frequency = frequencies[i].frequency;newNode->left = newNode->right = NULL;insertPriorityQueue(&pq, newNode);}// 重复合并节点，直到队列中只剩下一个节点，即哈夫曼树的根while (pq.front->next != NULL) {struct HuffmanNode* leftChild = extractMinPriorityQueue(&pq);struct HuffmanNode* rightChild = extractMinPriorityQueue(&pq);struct HuffmanNode* newNode = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));newNode->data = '\0'; // 内部节点没有字符数据newNode->frequency = leftChild->frequency + rightChild->frequency;newNode->left = leftChild;newNode->right = rightChild;insertPriorityQueue(&pq, newNode);}// 返回哈夫曼树的根节点return extractMinPriorityQueue(&pq);
}// 生成哈夫曼编码
void generateHuffmanCodes(struct HuffmanNode* root, int code[], int top) {if (root->left != NULL) {code[top] = 0;generateHuffmanCodes(root->left, code, top + 1);}if (root->right != NULL) {code[top] = 1;generateHuffmanCodes(root->right, code, top + 1);}if (root->left == NULL && root->right == NULL) {printf("Character: %c, Code: ", root->data);for (int i = 0; i < top; ++i) {printf("%d", code[i]);}printf("\n");}
}// 主函数
int main() {struct FrequencyTable frequencies[] = {{'A', 2}, {'B', 1}, {'C', 1}, {'D', 1},{'E',4}};int n = sizeof(frequencies) / sizeof(frequencies[0]);struct HuffmanNode* root = buildHuffmanTree(frequencies, n);int code[100];int top = 0;printf("Huffman Codes:\n");generateHuffmanCodes(root, code, top);return 0;
}

3、活动选择问题

活动选择问题（Activity Selection Problem）是一个经典的贪心算法问题，也称为区间调度问题。给定一组活动，每个活动都有一个开始时间和结束时间，目标是选择出最大可能的互不相交的活动子集。

以下是活动选择问题的算法思想：

  1. 将活动按照结束时间的先后顺序进行排序。
  2. 选择第一个活动作为初始活动，并将其加入最终选择的活动子集。
  3. 从第二个活动开始，依次判断每个活动是否与已选择的活动相容（即结束时间是否早于下一个活动的开始时间），如果相容，则将该活动加入最终选择的活动子集。
  4. 重复步骤3，直到遍历完所有活动。

通过贪心策略，每次选择结束时间最早的活动，可以确保选择的活动子集最大化。因为如果一个活动与已选择的活动相容，那么它一定是结束时间最早的活动，选择它不会影响后续活动的选择。
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码实现

该算法的核心就是 每次选择结束时间最早的活动

#include <stdio.h>
#include <stdlib.h>// 活动结构
struct Activity {int start;int end;
};// 比较函数，用于按结束时间升序排序
int compare(const void* a, const void* b) {return ((struct Activity*)a)->end - ((struct Activity*)b)->end;
}// 活动选择算法
void activitySelection(struct Activity activities[], int n) {// 按结束时间升序排序qsort(activities, n, sizeof(struct Activity), compare);// 第一个活动总是被选择printf("Selected activity: (%d, %d)\n", activities[0].start, activities[0].end);// 从第二个活动开始选择int lastActivity = 0;for (int i = 1; i < n; ++i) {// 如果活动的开始时间晚于或等于上一个已选择活动的结束时间，选择该活动if (activities[i].start >= activities[lastActivity].end) {printf("Selected activity: (%d, %d)\n", activities[i].start, activities[i].end);lastActivity = i;}}
}// 主函数
int main() {struct Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};int n = sizeof(activities) / sizeof(activities[0]);printf("Activity schedule:\n");activitySelection(activities, n);return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/208936.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Python图表神器：Matplotlib库绘制图表轻松有趣

Python图表神器：Matplotlib库绘制图表轻松有趣

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com Matplotlib是Python中用于绘制图表和数据可视化的重要库。它提供了丰富的功能和灵活性&#xff0c;可用于生成各种类型的图表&#xff0c;从简单的折线图到复杂的三维图表。 1. 基本图表绘制 折线图 Matplotl…
阅读更多...
TCP连接为什么是三次握手，而不是两次和四次

TCP连接为什么是三次握手，而不是两次和四次

答案 阻止重复的历史连接同步初始序列号避免资源浪费 原因 阻止重复的历史连接&#xff08;首要原因&#xff09; 考虑这样一种情况&#xff1a; 客户端现在要给服务端建立连接&#xff0c;向服务端发送了一个SYN报文段&#xff08;第一次握手&#xff09;&#xff0c;以表示请…
阅读更多...
Electron+Ts+Vue+Vite桌面应用系列：TypeScript常用时间处理工具

Electron+Ts+Vue+Vite桌面应用系列：TypeScript常用时间处理工具

文章目录 1️⃣ 时间处理工具1.1 格式化时间1.2 把时间戳改成日期格式1.3 Day.js 工具类使用1.4 date-fns 工具类使用 优质资源分享 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/134712978 ElectronTsVueVite桌面应用…
阅读更多...
TCP三次握手与四次挥手

TCP三次握手与四次挥手

TCP三次握手与四次挥手 TCP三次握手与四次挥手解析 客户端连接服务器&#xff08;三次握手&#xff09;客户端关闭与服务器连接&#xff08;四次挥手&#xff09; 总结 TCP三次握手与四次挥手、流量控制(滑动窗口)、拥塞控制、半连接状态、2MSL TCP三次握手与四次挥手 TCP标…
阅读更多...
深度学习-模型调试经验总结

深度学习-模型调试经验总结

1、 这句话的意思是&#xff1a;期望张量的后端处理是在cpu上&#xff0c;但是实际是在cuda上。排查代码发现&#xff0c;数据还在cpu上&#xff0c;但是模型已经转到cuda上&#xff0c;所以可以通过把数据转到cuda上解决。 解决代码&#xff1a; tensor.to("cuda")…
阅读更多...
分享66个焦点幻灯JS特效，总有一款适合您

分享66个焦点幻灯JS特效，总有一款适合您

分享66个焦点幻灯JS特效&#xff0c;总有一款适合您 66个焦点幻灯JS特效下载链接&#xff1a;https://pan.baidu.com/s/10bqe09IAZt_hbsZlXaxkxw?pwd6666 提取码&#xff1a;6666 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;…
阅读更多...
C++-内存管理

C++-内存管理

目录 一.C/C内存分布 二. C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 三. C内存管理方式 1.new/delete操作内置类型 2.new和delete操作自定义类型 四.C语言中的动态开辟内存空间和C中的区别 1.对于开辟内置类型 2.…
阅读更多...
office tool plus工具破解word、visio等软件步骤

office tool plus工具破解word、visio等软件步骤

第一步&#xff1a;下载工具 破解需要用到office tool plus软件 office tool plus软件下载地址&#xff1a;Office Tool Plus 官方网站 - 一键部署 Office 选择其中一个下载到本地&#xff08;本人选择的是第一个的云图小镇下载方式&#xff09; 第二步&#xff1a;启动工具 …
阅读更多...
群晖NAS：docker（Container Manager）、npm安装Verdaccio并常见命令集合

群晖NAS：docker（Container Manager）、npm安装Verdaccio并常见命令集合

群晖NAS&#xff1a;docker&#xff08;Container Manager&#xff09;、npm安装Verdaccio并常见命令集合 自建 npm 资源库&#xff0c;使用Verdaccio。如果觉得麻烦&#xff0c;直接可以在外网注册 https://www.npmjs.com/ 网站。大同小异&#xff0c;自己搭建搭建方便局域网…
阅读更多...
内存函数​（memcpy、memmove、memset、memcmp）

内存函数​（memcpy、memmove、memset、memcmp）

目录 一、memcpy的使用和实现 使用&#xff1a; 模拟实现&#xff1a; 二、memmove 使用和模拟实现 模拟实现&#xff1a; 2.1难点&#xff1a; 覆盖拷贝所在的问题 memset的使用 memcmp的函数的使用​ 一、memcpy的使用和实现 memcpy 拷贝的就是不重叠的内存。 参数…
阅读更多...
ChatGPT 的 18 种玩法，你还不会用吗？

ChatGPT 的 18 种玩法，你还不会用吗？

你确定&#xff0c;你会使用 ChatGPT 了吗&#xff1f; 今天给大家整理了 18 种 ChatGPT 的用法&#xff0c;看看有哪些方法是你能得上的。 用之前我们可以打开R5Ai平台&#xff0c;可以免费使用目前所有的大模型 地址&#xff1a;R5Ai.com 语法更正 用途&#xff1a;文章…
阅读更多...
ChatGPT 问世一周年之际，开源大模型能否迎头赶上？

ChatGPT 问世一周年之际，开源大模型能否迎头赶上？

就在11月30日&#xff0c;ChatGPT 迎来了它的问世一周年&#xff0c;这个来自 OpenAI 的强大AI在过去一年里取得了巨大的发展&#xff0c;迅速吸引各个领域的用户群体。 我们首先回忆一下 OpenAI和ChatGPT这一年的大事记&#xff08;表格由ChatGPT辅助生成&#xff09;&#x…
阅读更多...
c语言-联合体和枚举

c语言-联合体和枚举

文章目录 一、联合体1. 联合体类型的声明和创建2. 联合体的特点3. 联合体大小的计算4.总结 二、枚举1. 枚举类型的声明2. 枚举类型的优点3. 枚举类型的使用 一、联合体 &#xff08;1&#xff09; 像结构体⼀样&#xff0c;联合体也是由一个或者多个成员构成&#xff0c;这些成…
阅读更多...
Vue3实现滚动到容器底部时发送请求，加载新数据

Vue3实现滚动到容器底部时发送请求，加载新数据

问题来源 在项目中出现了需要在容器滚动到底部时&#xff0c;加载新的数据的需求&#xff0c;以下是解决的方案笔记 解决 画了个流程图&#xff1a; 如图&#xff0c;先添加一个动态加载的图标&#xff0c;还有全部数据载完的《到底啦...》 大概这么个样子&#xff0c;之后呢…
阅读更多...
SQL Server数据库部署

SQL Server数据库部署

数据库简介 使用数据库的必要性 使用数据库可以高效且条理分明地存储数据&#xff0c;使人们能够更加迅速、方便地管理数据。数据库 具有以下特点。 》可以结构化存储大量的数据信息&#xff0c;方便用户进行有效的检索和访问。 》 可以有效地保持数据信息的一致性&#xff0c…
阅读更多...
Button初了解

Button初了解

Button 由TextView派生而来&#xff0c;二者的区别有&#xff1a; Button有默认的按钮背景&#xff0c;TextView默认无背景Button的内部文本默认居中对齐&#xff0c;而TextView的默认靠左对齐2023年以前&#xff0c;Button默认将英文换为大写&#xff0c;而TextView保持原始的…
阅读更多...
大数据读本：暴雨以数字技术助力传统产业数字化转型

大数据读本：暴雨以数字技术助力传统产业数字化转型

发展数字经济&#xff0c;产业数字化是重要引擎。暴雨作为数字经济的领军企业&#xff0c;近年来积极利用数字技术对传统产业进行全方位、全角度、全链条的改造&#xff0c;提高要素生产率&#xff0c;释放数字对经济发展的放大、叠加、倍增作用。在农业产业化方面&#xff0c;…
阅读更多...
vue3请求代理proxy中pathRewrite失效

vue3请求代理proxy中pathRewrite失效

问题引入 在vue3配置请求代理proxy的时候pathRewrite失效。 有这样一个例子&#xff0c;作用是为了把所有以/api开头的请求代理到后端的路径和端口上&#xff0c;在vue.config.js配置文件中 设置了代理跨域和默认端口。但是重新运行之后发现端口是改了&#xff0c;但是路径仍然…
阅读更多...
维基百科文章爬虫和聚类：高级聚类和可视化

维基百科文章爬虫和聚类：高级聚类和可视化

一、说明 维基百科是丰富的信息和知识来源。它可以方便地构建为带有类别和其他文章链接的文章&#xff0c;还形成了相关文档的网络。我的 NLP 项目下载、处理和应用维基百科文章上的机器学习算法。 在我的上一篇文章中&#xff0c;KMeans 聚类应用于一组大约 300 篇维基百科文…
阅读更多...
Redis 数据结构详解

Redis 数据结构详解

分类 编程技术 Redis 数据类型分为&#xff1a;字符串类型、散列类型、列表类型、集合类型、有序集合类型。 Redis 这么火&#xff0c;它运行有多块&#xff1f;一台普通的笔记本电脑&#xff0c;可以在1秒钟内完成十万次的读写操作。 原子操作&#xff1a;最小的操作单位&a…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发