计算机算法分析与设计(11)---贪心算法(活动安排问题和背包问题)

文章目录

  • 一、贪心算法概述
  • 二、活动安排问题
    • 2.1 问题概述
    • 2.2 代码编写
  • 三、背包问题
    • 3.1 问题描述
    • 3.2 代码编写


一、贪心算法概述

 1. 贪心算法的定义:贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。

 2. 注意:贪心算法对有些问题可以快速获得整体最优解。对有些问题虽不能得到整体最优解,却可以得到近似最优解。

 3. 用贪心算法求解问题要满足以下条件:

  • 贪心选择性质:贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来得到,即通过贪心选择来达到。
  • 最优子结构性质:一个问题的最优解包含其子问题的最优解。

 4. 贪心算法与动态规划的差异:

  • 相同:贪心算法和动态规划算法都要求问题具有最优子结构性质。
  • 不同:动态规划算法通常以自底向上的方式解各子问题;贪心算法通常以自顶往下的方式进行,每做一次贪心选择就将问题简化为规模更小的子问题。

 5. 贪心算法解题的一般步骤是:

  • 建立数学模型来描述问题。
  • 把求解的问题分成若干个子问题。
  • 对每一子问题求解,得到子问题的局部最优解。
  • 把子问题的局部最优解合成原来问题的一个解。

二、活动安排问题

2.1 问题概述

 1. 有 n n n 个需要在同一天使用同一个教室的活动: a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an。教室同一时刻只能由一个活动使用。每个活动 a i a_i ai 都有一个开始时间 s i s_i si 和结束时间 f i f_i fi。一旦被选择后,活动 a i a_i ai 就占据半开时间区间 [ s i , f i ) [s_i,f_i) [si,fi)。如果 [ s i , f i ) [s_i,f_i) [si,fi) [ s j , f j ) [s_j,f_j) [sj,fj) 互不重叠, a i a_i ai a j a_j aj 两个活动就可以被安排在这一天。该问题就是要安排这些活动,使得尽量多的活动能不冲突地举行。

 2. 可以用数学归纳法证明,我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解,按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。

在这里插入图片描述

2.2 代码编写

 1. 不需要我们排序的代码:

#include<bits/stdc++.h>  
using namespace std; void activity_select(int n, int s[], int f[], int selected[])
{int j = 1; //j记录最近一次加入的活动 selected[1] = 1; //首先选择活动1 for (int i = 2; i <= n; i ++)if (s[i] >= f[j]) //如果活动i与活动j兼容,则选择活动i{  selected[i] = 1;j = i;}else{selected[i] = 0;}
}int main()
{cout<<"请输入活动的个数:"; int n;cin>>n;int s[n],f[n];  //s[i],f[i]存储活动i的开始和结束时间int selected[n];  //若活动i被选择,则selected[i]置1,否则置0cout<<"请输入活动的开始和结束时间(按照结束时间升序输入):"<<endl;for (int i = 1; i <= n; i++){cin>>s[i]>>f[i];}activity_select(n,s,f,selected);cout<<"有如下活动被选择:"<<endl;for (int i = 1; i <= n; i++){if (selected[i] == 1){cout<<i<<" "; }}	return 0;
}

 2. 需要我们排序的代码:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;    struct activity //活动结构体 
{int start;int end;
};bool cmp(activity a,activity b)  //cmp参数为sort函数的排序准则,设置为按照活动的结束时间由小到大排序 
{  return a.end<b.end;  
} void activity_select(int n,int selected[],activity act[])  
{  int i=1;selected[1]=1; for(int j=2;j<=n;j++)  //从结束时间倒数第二小的活动开始遍历 {  if(act[j].start>=act[i].end)  {  i=j;   selected[j]=1; }  else{selected[j]=0;}}  
}int main()  
{cout<<"请输入活动的个数:";int n;cin>>n;int selected[n]; //若活动i被选择,则selected[i]置1,否则置0activity act[n];cout<<"请输入活动的开始和结束时间(按照结束时间升序输入):"<<endl;   for(int i=1;i<=n;i++){cin>>act[i].start>>act[i].end;}act[0].start=-1;act[0].end=-1;sort(act+1,act+n+1,cmp); //act+1表示第2个元素(i=1,第1个活动) activity_select(n,selected,act);  cout<<"有如下活动被选择:"<<endl;for (int i=1; i<=n; i++){if (selected[i]==1){cout<<i<<" "; }}	return 0;
}  

三、背包问题

3.1 问题描述

 1. 假设有 n n n 件物品,每件物品 i i i 对应价值为 v i v_i vi,重量 w i w_i wi。背包只能装入重量为 m m m 的物品。每件物品只能拿 1 1 1 件,可以分割。问题是怎样放使得背包装入的物品价值最大?

 2. 贪心策略:(1)每次挑选价值最大的物品装入背包,得到的结果是否最优?(2)每次挑选重量最小的物品装入背包,得到的结果是否最优?(3)每次挑选单位重量价值最大的物品,价值是否最高?

 3. 可以用数学归纳法证明,我们的贪心策略应该是每次选取单位重量价值最大的的物品。

在这里插入图片描述

在这里插入图片描述

3.2 代码编写

#include<bits/stdc++.h>
using namespace std; struct item_type
{float weight; //物品重量 float value; //物品价值 float per_item_value; //单位重量物品价值 float rate; //使用百分率 
};bool cmp(item_type a, item_type b)
{return a.per_item_value > b.per_item_value;
}int main()
{int n; //n个物品float c; //背包容量为ccout << "输入物品件数和背包容量:" << endl;cin >> n >> c;item_type item[n];item[0].per_item_value=0;item[0].rate=0;item[0].value=0;item[0].weight=0;cout << "依次输入每件物品的价值和重量:" << endl;for (int i = 1; i <= n; i++){cin >> item[i].value >> item[i].weight;item[i].per_item_value = item[i].value / item[i].weight;//计算性价比item[i].rate = 0;//初始化使用率}sort(item + 1, item + n + 1, cmp);float sum = 0;int j = 1;for (j = 1; j < n; j++){if (item[j].weight <= c){item[j].rate = 1;sum = sum + item[j].value;c = c - item[j].weight; //c一直在更新 cout << "重量为:" << item[j].weight << "价值为:" << item[j].value << "的物品被放入了背包,放入比例为:" << item[j].rate << endl;}elsebreak;}//物品没装完if (j < n){item[j].rate = c / item[j].weight;c = c - item[j].rate * item[j].weight;sum = sum + item[j].rate * item[j].value;cout << "重量为:" << item[j].weight << "价值为:" << item[j].value << "的物品被放入了背包,放入比例为:" << item[j].rate << endl;cout << "背包剩余容量为:" << c;cout << "总价值:" << sum;}return 0; 
}

在这里插入图片描述

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

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

相关文章

使用轮廓分数提升时间序列聚类的表现

我们将使用轮廓分数和一些距离指标来执行时间序列聚类实验&#xff0c;并且进行可视化 让我们看看下面的时间序列: 如果沿着y轴移动序列添加随机噪声&#xff0c;并随机化这些序列&#xff0c;那么它们几乎无法分辨&#xff0c;如下图所示-现在很难将时间序列列分组为簇: 上面…

day35

今日内容概要 Socket抽象层(socket编程) 基于TCP协议的借助socket可以编程客户端和服务端的程序 链接循环 通信循环 基于UDP协议的套接字(socket)编程 粘包现象 如何解决粘包现象(重要的是解决的思路) struct模块的使用(打包、解包) 今日内容详细 Socket抽象层&#x…

【Java学习之道】TCPIP套接字编程实例

引言 网络编程是Java学习中不可或缺的一部分&#xff0c;而TCP/IP套接字编程又是网络编程的基础。那么&#xff0c;初学者如何才能快速掌握TCP/IP套接字编程呢&#xff1f;今天我们就来通过一个简单的实例&#xff0c;为你揭示TCP/IP套接字编程的奥秘&#xff01; 一、什么是…

2023_Spark_实验十四:SparkSQL入门操作

1、将emp.csv、dept.csv文件上传到分布式环境&#xff0c;再用 hdfs dfs -put dept.csv /input/ hdfs dfs -put emp.csv /input/ 将本地文件put到hdfs文件系统的input目录下 2、或者调用本地文件也可以。区别&#xff1a;sc.textFile("file:///D:\\temp\\emp.csv&qu…

学信息系统项目管理师第4版系列29_信息系统治理

1. IT治理 1.1. 描述组织采用有效的机制对信息技术和数据资源开发利用&#xff0c;平衡信息化发展和数字化转型过程中的风险&#xff0c;确保实现组织的战略目标的过程 1.2. 驱动因素 1.2.1. 信息孤岛 1.2.2. 信息资源整合目标空泛 1.3. 高质量IT治理因素 1.3.1. 良好的I…

哈佛教授因果推断力作:《Causal Inference: What If 》pdf下载

因果推断是一项复杂的科学任务&#xff0c;它依赖于多个来源的三角互证和各种方法论方法的应用&#xff0c;是用于解释分析的强大建模工具&#xff0c;同时也是机器学习领域的热门研究方向之一。 今天我要给大家推荐的这本书&#xff0c;正是因果推断领域必读的入门秘籍&#…

UGUI交互组件InputField

一.InputField的结构 对象说明InputField挂有TextMeshPro-InputField组件的主体对象Text Area文本显示区Placeholder未输入时占位文本Enter text...Text输入的显示文本 二.InputField的属性 属性说明Text ViewportText Area子对象的引用Text ComponentText子对象的引用Text输入…

Latex 通过\item控制编号

\item通常用于 1 论文写作中的hightlight 2 或一些需要缩进的场景 具体实现 \item 或\item[]在方括号里面添加1&#xff09;、 (1)来控制

visual studio安装时候修改共享组件、工具和SDK路径方法

安装了VsStudio后,如果自己修改了Shared路径&#xff0c;当卸载旧版本&#xff0c;需要安装新版本时发现&#xff0c;之前的Shared路径无法进行修改&#xff0c;这就很坑爹了&#xff0c;因为我运行flutter程序的时候&#xff0c;报错找不到windows sdk的位置&#xff0c;所以我…

Open3D 进阶(13)使用PCA将点云投影到主成分空间

目录 一、算法原理<font color="#dd00dd">1、三维点云投影二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。爬虫网站自重。 一、算法原理 1、三维点云投影 p r o j

手机抬手亮屏解锁,用到了哪些硬件?

随着时代发展&#xff0c;智能手机以丰富的功能及便利性&#xff0c;成为了人们必不可少的物品&#xff0c;其中人脸解锁功能是非常有用的功能&#xff0c;广受年轻人的喜爱&#xff0c;那么你知道她是如何实现吗&#xff1f;今天凡小亿带你们探索&#xff01; 手机抬手亮屏解锁…

BAT026:删除当前目录指定文件夹以外的文件夹

引言&#xff1a;编写批处理程序&#xff0c;实现删除当前目录指定文件夹以外的文件夹。 一、新建Windows批处理文件 参考博客&#xff1a; CSDNhttps://mp.csdn.net/mp_blog/creation/editor/132137544 二、写入批处理代码 1.右键新建的批处理文件&#xff0c;点击【编辑】…

在 Windows Server RDS 服务器 上重置 120 天宽限期

如果您出于测试目的安装了 RDS Server 2016/2019/2022&#xff0c;并且 RDS 许可宽限期已过期&#xff0c;请继续阅读下面的内容以了解如何重置 120 天宽限期。您可能知道&#xff0c;在安装 RDS Server 2016 时&#xff0c;您有 120 天的时间来安装 RD 客户端访问许可证 &…

【设计模式】单例模式、“多例模式”的实现以及对单例的一些思考

文章目录 1.概述2.单例模式实现代码2.1.饿汉式单例2.2.懒汉式单例2.3.双检锁单例2.4.静态内部类单例2.5.枚举单例 3.对单例的一些思考3.1.是否需要严格的禁止单例被破坏&#xff1f;3.2.懒汉式真的比饿汉式更佳吗&#xff1f;3.3.单例存在的问题 4.其他作用范围的单例模式4.1.线…

jenkins出错与恢复

如果你的jenkins出现了如下图所示问题&#xff08;比如不能下载插件&#xff0c;无法保存任务等&#xff09;&#xff0c;这个时候就需要重新安装了。 一、卸载干净jenknis 要彻底卸载 Jenkins&#xff0c;您可以按照以下步骤进行操作&#xff1a; 1、停止 Jenkins 服务&…

官方认证:研发效能(DevOps)工程师职业技术认证

培养端到端的研发效能人才 为贯彻落实《关于深化人才发展体制机制改革的意见》&#xff0c;推动实施人才强国战略&#xff0c;促进专业技术人员提升职业素养、补充新知识新技能&#xff0c;实现人力资源深度开发&#xff0c;推动经济社会全面发展&#xff0c;根据《中华人民共…

Vue检测数据的原理

Vue能够对用户的数据进行响应式&#xff0c;也就是你在data中写了什么&#xff0c;你在模板中用到data的部分就会渲染成什么&#xff0c;那么Vue是怎么知道用户修改了data中的数据变化并对模板重新进行解析的呢&#xff1f; 在Vue将数据存储为自身的_data之前&#xff0c;Vue会…

【软考-中级】系统集成项目管理工程师 【18 风险管理】

持续更新。。。。。。。。。。。。。。。 【第十八章】风险管理 (选择3分&#xff0c;偶尔案例18 分 18.1 风险概述18.1.1 风险的定义18.1.2 风险的分类18.1.3 风险的性质 18.2 项目风险管理18.3 规划风险管理18.3.1 规划风险管理的输入18.3.2 规划风险管理的工具与技术18.3.3 …

解决安装nvm以后windows cmd无法找到npm/yarn命令的问题

安装了nodejs多版本管理工具nvm以后&#xff0c;会出现windows cmd无法找到npm/yarn命令的问题 只要一运行npm/yarn就会提示&#xff1a;不是内部命令&#xff0c;找不到运行路径之类的。 解决办法&#xff1a;首先打开windows环境变量的配置&#xff0c;查看NVM_SYMLINK指向…

在nodejs中实现调度任务

在nodejs中实现调度任务 node.js帮助开发人员简化了工作流程&#xff0c;创建了高效的应用程序。它的许多有用功能之一是任务调度。本文将探讨在nodejs中调度任务的重要性、各种使用第三方库的代码示例&#xff0c;以及需要遵循的一些有用的操作。 为什么我们需要安排任务 调…