没有合适的资源?快使用搜索试试~ 我知道了~
首页贪心算法详解:实例与应用
贪心算法详解:实例与应用
需积分: 0 1 下载量 65 浏览量
更新于2024-06-18
收藏 233KB DOCX 举报
"该Word文档深入探讨了贪心算法这一关键的算法思想,它是一种在解决问题时采取局部最优决策,以期望达到全局最优解的方法。贪心算法适用于那些具有贪心选择性质和最优子结构特性的问题,其中贪心选择性质指的是问题的整体最优解可以通过一系列局部最优解实现,且每一步选择独立于后续决策;而最优子结构则意味着问题的最优解由其子问题的最优解组合而成。 文档详细阐述了贪心算法的解题步骤:首先,通过建立数学模型描述问题;接着,将问题分解为子问题,针对每个子问题寻找局部最优解;然后,将子问题的解合并成原问题的完整解决方案。文档还举例说明了经典的贪心算法应用实例,如钱币找零问题。在这个问题中,算法的核心思想是优先使用面额较大的纸币来减少所需纸币的总数,直至支付完毕指定金额。代码示例展示了如何通过循环实现这一过程。 此外,文档还提到了其他一些常见的贪心算法应用,例如活动选择问题、区间覆盖问题、小船过河问题、Dijkstra最短路径算法以及Prim最小生成树算法等。这些例子进一步展示了贪心算法在实际问题中的实用性。对于非0-1背包问题,虽然文档未提供具体链接,但通常这类问题也遵循贪心策略,通过每次选择当前价值最大或收益最大的物品,以求解部分背包问题的最优解。 这份文档深入讲解了贪心算法的基本概念、适用条件、解题策略以及多个实例,为理解和应用贪心算法提供了全面的学习资料。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88717383/bg7.jpg)
【思路】:
两种方法,较容易想到的是第一种方式:
第一种办法:先让1 2过去(2分钟),1回来(1分钟),1 5过去(5分钟),1回来(1分钟),
1 10再过去(10分钟),总共需要19分钟就可以让四个人都过去。
而正确答案是第二种办法:先让1 2过去(2分钟),1回来(1分钟),5 10过去(10分钟),
2回来(2分钟),1 2再过去(2分钟),总共需要17分钟就可以让四个人都过去。
本题的关键在于把最慢的和次慢的两个人运过河,因此只要大于四个人的情况下:
只需要将这两种方式这两个人运过河的时间做对比:
第一种:T4 + T1 + T3 + T1
第二种:T2 + T1 + T4 + T2
对比之后取短的就行
在人数 >= 4时,该问题的解决思路常常有两种:
1.最快的和次快的过河,然后最快的将船划回来;次慢的和最慢的过河,
然后次快的将船划回来。此时我们可以计算一下这个过程所花费的时间
(至于为什么要计算这个过程所花费的时间,因为当人数 >= 4时,
一直将这个过程重复下去即可)
2.最快的和最慢的过河,然后最快的将船划回来,最快的和次慢的过河,
然后最快的将船划回来。
【参考代码】:
int cross(int a[], int n)
{
sort(a, a + n);//排序之后最慢的在最后面
int time = 0;
//负责将最慢和次慢的人运过河
while (n > 3)
{//比较看谁更快一点
if ( (2 * a[0] + a[n - 2] + a[n - 1]) <= (2 * a[1] + a[0] + a[n - 1]) )
time = time + 2 * a[0] + a[n - 2] + a[n - 1];
else
time = time + 2 * a[1] + a[0] + a[n - 1];
n = n - 2;//运过去两个人(最慢和次慢)
}
if (n == 3)
time = time + a[0] + a[1] + a[n - 1];
if (n == 2)
time = time + a[n - 1];//回来接最后一个人回去
if (n == 1)
time = time + a[0];//自己回去
return time;
![](https://csdnimg.cn/release/download_crawler_static/88717383/bg8.jpg)
}
int main()
{
int n;//输入一共多少个人过河
cin >> n;
int a[100000] = { 0 };
for (int i = 0; i < n; i++)
cin >> a[i];//输入每个人过河的时间
cout << cross(a, n) << endl;
return 0;
}
【输出结果】
Dijkstra 最短路径算法(图)
【参考代码】
SequenceList.h 头文件
#pragma once
typedef struct
{
int list[MaxSize];
int size;
}SequenceList;
void ListInitialize(SequenceList *L)
{
L->size = 0;
}
int ListLength(SequenceList L)
{
return L.size;
}
剩余36页未读,继续阅读
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/bcbcf2d1e3a845a5b94b6c27332c1a6b_ch3ch2ch4.jpg!1)
做人求其滴
- 粉丝: 523
- 资源: 5
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)