当前位置: 首页 > news >正文

计算机算法分析与设计(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; 
}

在这里插入图片描述

相关文章:

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

文章目录 一、贪心算法概述二、活动安排问题2.1 问题概述2.2 代码编写 三、背包问题3.1 问题描述3.2 代码编写 一、贪心算法概述 1. 贪心算法的定义&#xff1a;贪心算法是指在对问题求解时&#xff0c;总是做出在当前看来是最好的选择。也就是说&#xff0c;不从整体最优上加以…...

shell命令以及运行原理

Linux严格意义上说的是一个操作系统&#xff0c;我们称之为“核心&#xff08;kernel&#xff09;“ &#xff0c;但我们一般用户&#xff0c;不能直接使用kernel。 而是通过kernel的“外壳”程序&#xff0c;也就是所谓的shell&#xff0c;来与kernel沟通。如何理解&a…...

MySQL进阶(再论JDBC)——JDBC编程思想的分析 JDBC的规范架构 JDBC相关的类分析

前言 SQL&#xff08;Structured Query Language&#xff09;是一种用于管理关系型数据库的标准化语言&#xff0c;它用于定义、操作和管理数据库中的数据。SQL是一种通用的语言&#xff0c;可以用于多种关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;如MySQ…...

rabbitMQ的知识点

RabbitMQ是一种消息队列软件&#xff0c;它实现了高度可靠的消息传递机制。RabbitMQ支持多种消息协议&#xff0c;包括AMQP、STOMP、MQTT等&#xff0c;比较灵活。以下是一些rabbitmq的知识点&#xff1a; 1. 消息队列&#xff1a;消息队列是一种分布式系统中广泛使用的通信模…...

​EtherNet/IP 库卡机器人和EtherCAT倍福PLC总线协议连接案例​

EtherNet/IP 是一种适合于工业环境和对时间要求比较苛刻的应用的网络。而远创智控YC-EIPM-ECT通讯网关&#xff0c;是一款自主研发的EtherNet/IP 从站功能的通讯网关。它不仅可以实现EtherNet/IP 和EtherCAT的无缝连接&#xff0c;还可以将EtherNet/IP 作为从站连接到EtherCAT总…...

微信小程序 uniapp+vue线上洗衣店业务管理系统演89iu2

本课题意在设计一种系统的、基于用户体验的线上洗衣服务模式&#xff0c;具有如下的研究意义: (1)为用户提供更简单、便捷的洗衣服务模式; (2)为智能柜的盈利模式提供了新的方向; (3)通过线上系统、智能柜与洗衣工厂结合的方式&#xff0c;为洗衣企业构建了一套节 省人力成本的…...

Maven项目,进行编译,使用idea的 编译功能,就是正常的,但是在终端中执行 mvn clean compile 报错

一、背景&#xff1a; Maven项目&#xff0c;进行编译&#xff0c;使用idea的 编译功能&#xff0c;就是正常的&#xff0c;但是在终端中执行 mvn clean compile 报错 报错信息&#xff1a; [ERROR] Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin…...

mssql还原数据库失败

标题: Microsoft SQL Server Management Studio ------------------------------ 服务器 "192.168.31.132" 的 附加数据库 失败。 (Microsoft.SqlServer.Smo) 有关帮助信息&#xff0c;请单击: https://go.microsoft.com/fwlink?ProdNameMicrosoftSQLServer&…...

Linux多线程编程- 无名信号量

简介 无名信号量&#xff08;在 POSIX 环境下通常指 sem_t 类型的信号量&#xff09;是用于同步和互斥的原语&#xff0c;它允许线程和进程按照预期的顺序执行&#xff0c;并确保对共享资源的安全访问。无名信号量与命名信号量的主要区别在于它们的可见性和生命周期。无名信号…...

【网络协议】聊聊DHCP和PXE 工作原理

DHCP 动态主机配置协议 对于每个主机来说&#xff0c;只要连接了网络&#xff0c;那么就会配置一个IP地址&#xff0c;那么这个IP地址&#xff0c;如果是手动配置的话&#xff0c;对于公司内部的人员来说都要找IT进行配置&#xff0c;这个太浪费人力物力了&#xff0c;所以解决…...

发现国内优秀的团队协作软件,帮助提高工作效率

中国有许多优秀的团队协作软件&#xff0c;它们在企业和组织中发挥着重要作用。 以下是一些最受欢迎的团队协作软件&#xff1a; 1、钉钉&#xff08;DingTalk&#xff09;: 这是一款由阿里巴巴推出的企业级协作工具&#xff0c;旨在帮助企业和组织实现高效沟通和协作。钉钉提…...

LeetCode 面试题 08.12. 八皇后

文章目录 一、题目二、C# 题解 一、题目 设计一种算法&#xff0c;打印 N 皇后在 N N 棋盘上的各种摆法&#xff0c;其中每个皇后都不同行、不同列&#xff0c;也不在对角线上。这里的“对角线”指的是所有的对角线&#xff0c;不只是平分整个棋盘的那两条对角线。 注意&#…...

Excel 的下拉列表

可以将 Sheet6 隐藏&#xff0c;就更好地隐藏了来源。...

基于Effect的组件设计 | 京东云技术团队

Effect的概念起源 从输入输出的角度理解Effect https://link.excalidraw.com/p/readonly/KXAy7d2DlnkM8X1yps6L 编程中的Effect起源于函数式编程中纯函数的概念 纯函数是指在相同的输入下&#xff0c;总是产生相同的输出&#xff0c;并且没有任何副作用(side effect)的函数。…...

541. 反转字符串 II

541. 反转字符串 II class Solution { public:void Reverse(string& s, int start, int end){end--;while (start < end){swap(s[start], s[end]);start;end--;}}string reverseStr(string s, int k){int len s.size();for (int i 0; i < len; i 2 * k){if (i …...

基本分段存储管理方式(分段,段表,地址转换以及与分页管理对比)

1.分段 1.进程的地址空间: 按照程序自身的逻辑关系划分为若干个段&#xff0c;每个段都有一个段名 &#xff08;在低级语言中&#xff0c;程序员使用段名来编程&#xff09;&#xff0c;每段从0开始编址. 2.内存分配规则: 以段为单位进行分配&#xff0c;每个段在内存中占据…...

哪个牌子的洗地机好用?2023洗地机推荐

洗地机作为一款高效的清洁家电能轻松的搞定各种干湿垃圾&#xff0c;满足日常生活中的各种地面清洁需求&#xff0c;越来越受大众的青睐&#xff0c;那么我们如何快速的选择一款适合自己无线洗地机呢?一起来看看! 做推荐之前&#xff0c;先给大家科普选购洗地机的时候应该关注…...

根据脑图谱获取感兴趣区域的mask

根据脑图谱获取感兴趣区域的mask 1&#xff0c;引入1.1 ASPECT-Atlas 2&#xff0c;获取脑图谱感兴趣区域mask参考&#xff1a; 1&#xff0c;引入 脑影像分析中&#xff0c;我们常常会针对性的对某些感兴趣区域进行分析&#xff0c;而对它们进行分析的前提是获取该区域的mask…...

Android Framework通信:Handler

文章目录 前言一、Handler源码分析1、创建Handler2、发送消息3、取消息4、消息处理5、线程切换的方法&#xff08;Handler异步消息处理机制流程&#xff09;handler.sendMessage()handler.post()View.post()Activity中的runOnUiThread() 二、Handler高频面试题1、为什么要有Han…...

Redis的安装和配置

一、Redis的安装 使用命令将redis安装到linux服务器 yum -y install redis配置redis配置文件 redis的配置文件默认路径为/etc/redis.conf&#xff0c;对配置文件进行修改。 &#xff08;1&#xff09;注释掉bind 127.0.0.1&#xff1b; bind配置项设置的是redis允许的ip地址访问…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...