计算机算法分析与设计(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. 贪心算法的定义:贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以…...

shell命令以及运行原理
Linux严格意义上说的是一个操作系统,我们称之为“核心(kernel)“ ,但我们一般用户,不能直接使用kernel。 而是通过kernel的“外壳”程序,也就是所谓的shell,来与kernel沟通。如何理解&a…...

MySQL进阶(再论JDBC)——JDBC编程思想的分析 JDBC的规范架构 JDBC相关的类分析
前言 SQL(Structured Query Language)是一种用于管理关系型数据库的标准化语言,它用于定义、操作和管理数据库中的数据。SQL是一种通用的语言,可以用于多种关系型数据库管理系统(RDBMS),如MySQ…...
rabbitMQ的知识点
RabbitMQ是一种消息队列软件,它实现了高度可靠的消息传递机制。RabbitMQ支持多种消息协议,包括AMQP、STOMP、MQTT等,比较灵活。以下是一些rabbitmq的知识点: 1. 消息队列:消息队列是一种分布式系统中广泛使用的通信模…...

EtherNet/IP 库卡机器人和EtherCAT倍福PLC总线协议连接案例
EtherNet/IP 是一种适合于工业环境和对时间要求比较苛刻的应用的网络。而远创智控YC-EIPM-ECT通讯网关,是一款自主研发的EtherNet/IP 从站功能的通讯网关。它不仅可以实现EtherNet/IP 和EtherCAT的无缝连接,还可以将EtherNet/IP 作为从站连接到EtherCAT总…...

微信小程序 uniapp+vue线上洗衣店业务管理系统演89iu2
本课题意在设计一种系统的、基于用户体验的线上洗衣服务模式,具有如下的研究意义: (1)为用户提供更简单、便捷的洗衣服务模式; (2)为智能柜的盈利模式提供了新的方向; (3)通过线上系统、智能柜与洗衣工厂结合的方式,为洗衣企业构建了一套节 省人力成本的…...
Maven项目,进行编译,使用idea的 编译功能,就是正常的,但是在终端中执行 mvn clean compile 报错
一、背景: Maven项目,进行编译,使用idea的 编译功能,就是正常的,但是在终端中执行 mvn clean compile 报错 报错信息: [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) 有关帮助信息,请单击: https://go.microsoft.com/fwlink?ProdNameMicrosoftSQLServer&…...
Linux多线程编程- 无名信号量
简介 无名信号量(在 POSIX 环境下通常指 sem_t 类型的信号量)是用于同步和互斥的原语,它允许线程和进程按照预期的顺序执行,并确保对共享资源的安全访问。无名信号量与命名信号量的主要区别在于它们的可见性和生命周期。无名信号…...

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

发现国内优秀的团队协作软件,帮助提高工作效率
中国有许多优秀的团队协作软件,它们在企业和组织中发挥着重要作用。 以下是一些最受欢迎的团队协作软件: 1、钉钉(DingTalk): 这是一款由阿里巴巴推出的企业级协作工具,旨在帮助企业和组织实现高效沟通和协作。钉钉提…...
LeetCode 面试题 08.12. 八皇后
文章目录 一、题目二、C# 题解 一、题目 设计一种算法,打印 N 皇后在 N N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。 注意&#…...

Excel 的下拉列表
可以将 Sheet6 隐藏,就更好地隐藏了来源。...

基于Effect的组件设计 | 京东云技术团队
Effect的概念起源 从输入输出的角度理解Effect https://link.excalidraw.com/p/readonly/KXAy7d2DlnkM8X1yps6L 编程中的Effect起源于函数式编程中纯函数的概念 纯函数是指在相同的输入下,总是产生相同的输出,并且没有任何副作用(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.进程的地址空间: 按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名 (在低级语言中,程序员使用段名来编程),每段从0开始编址. 2.内存分配规则: 以段为单位进行分配,每个段在内存中占据…...

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

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

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

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

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...