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

计算机算法分析与设计(13)---贪心算法(多机调度问题)

文章目录

  • 一、问题概述
    • 1.1 思路分析
    • 1.2 实例分析
  • 二、代码编写


一、问题概述

1.1 思路分析

 1. 设有 n n n 个独立的作业 1 , 2 , … , n {1, 2, …, n} 1,2,,n,由 m m m 台相同的机器 M 1 , M 2 , … , M m {M_1, M_2, …, M_m} M1,M2,,Mm 进行加工处理,作业 i i i 所需的处理时间为 t i ( 1 ≤ i ≤ n ) t_i(1≤i≤n) ti(1in),每个作业均可在任何一台机器上加工处理,但不可间断、拆分。多机调度问题要求给出一种作业调度方案,使所给的 n n n 个作业在尽可能短的时间内由 m m m 台机器加工处理完成。

 2. 解决思路:(1)如果 n < m n<m n<m,这种情况很简单,将 n n n 个作业分配给 m m m 个机器中的 n n n 个就可以了。(2)如果 n > m n>m n>m,则用贪心算法求解。

 3. 贪心算法求解多机调度问题的贪心策略是最长处理时间的作业优先,即把处理时间最长的作业分配给最先空闲的机器,这样可以保证处理时间长的作业优先处理,从而在整体上获得尽可能短的处理时间。

1.2 实例分析

 设 7 7 7 个独立作业 1 , 2 , 3 , 4 , 5 , 6 , 7 {1, 2, 3, 4, 5, 6, 7} 1,2,3,4,5,6,7 3 3 3 台机器 M 1 , M 2 , M 3 {M1, M2, M3} M1,M2,M3 加工处理,各作业所需的处理时间分别为 2 , 14 , 4 , 16 , 6 , 5 , 3 {2, 14, 4, 16, 6, 5, 3} 2,14,4,16,6,5,3。贪心算法产生的作业调度如下图所示。所需要的加工时间为17。

在这里插入图片描述

二、代码编写

#include<bits/stdc++.h>
using namespace std;bool compare(int a,int b)
{return a>b;}int main(){int n,m; //作业个数为n, 机器个数为mcout<<"请输入作业和机器的个数:"<<endl; cin>>n>>m;vector<int> time(n);//vector<vector<int> > machine(m); //理解成m×1二维数组 vector<int> sumTime(m,0); //0表示初始化值为0 cout<<"请输入每个作业的处理时间:"<<endl; for(int i=0;i<n;i++){cin>>time[i];}sort(time.begin(),time.end(),compare); //对time进行排序,从大到小。for(int i=0;i<n;i++){int select=0;for(int j=0;j<m;j++){if(sumTime[j]<sumTime[select]){select=j;}}//machine[select].push_back(time[i]);sumTime[select]=sumTime[select]+time[i];	}int maxTime=sumTime[0];for(int j=0;j<m;j++){if(sumTime[j]>maxTime){maxTime=sumTime[j];}}for(int j=0;j<m;j++){cout<<"第"<<j+1<<"台机器所需处理总时间为: "<<sumTime[j]<<endl; }cout<<"处理所有作业时间共需: "<<maxTime;return 0;
}

在这里插入图片描述

相关文章:

计算机算法分析与设计(13)---贪心算法(多机调度问题)

文章目录 一、问题概述1.1 思路分析1.2 实例分析 二、代码编写 一、问题概述 1.1 思路分析 1. 设有 n n n 个独立的作业 1 , 2 , … , n {1, 2, …, n} 1,2,…,n&#xff0c;由 m m m 台相同的机器 M 1 , M 2 , … , M m {M_1, M_2, …, M_m} M1​,M2​,…,Mm​ 进行加工处…...

小程序canvas层级过高真机遮挡组件的解决办法

文章目录 问题发现真机调试问题分析问题解决改造代码效果展示 问题发现 在小程序开发中需要上传图片进行裁剪&#xff0c;在实际真机调试中发现canvas层遮挡住了生成图片的按钮。 问题代码 <import src"../we-cropper/we-cropper.wxml"></import> <…...

番外8.1 配置+管理文件系统

Task01: Linux 文件系统结构&#xff1b; 可以进行Linux操作系统的文件权限管理与方式切换&#xff0c;可以应用磁盘与文件权限管理工具&#xff1b; 01&#xff1a;常见文件系统类型&#xff08;Ext4[rhel6默认文件管理系统], 存储容量1 EB1073741824 GB; XFS[rhel 7/8默认的文…...

互联网Java工程师面试题·Java 总结篇·第八弹

目录 72、用 Java 的套接字编程实现一个多线程的回显&#xff08;echo&#xff09;服务器。 73、XML 文档定义有几种形式&#xff1f;它们之间有何本质区别&#xff1f;解析XML 文档有哪几种方式&#xff1f; 74、你在项目中哪些地方用到了 XML&#xff1f; 72、用 Java 的套…...

VSCode修改扩展和用户文件夹目录位置(Windows)

VSCode修改扩展和用户文件夹目录位置&#xff08;Windows&#xff09; 前言&#xff1a;方法前期准备&#xff1a;方法1&#xff08;强推荐&#xff09;方法2&#xff08;不太推荐&#xff09;方法3&#xff08;好麻烦&#xff0c;不太推荐&#xff09; 前言&#xff1a; VSCod…...

Spring 事务

文章目录 实现CURD&#xff08;没加入事务前&#xff09;1.加入依赖2.创建jdbc.properties3.配置Spring的配置文件4.数据库与测试表 基于注解的声明式事务准备工作测试模拟场景 加入事务①添加事务配置 Transactional注解标识的位置只读事务属性&#xff1a;超时事务属性&#…...

无法访问 github ,解决办法

一、使用代理&#xff08;首选&#xff09; 这种办法只需要更改github.com为代理的域名即可&#xff0c;使用方式与GitHub除了域名不同其他都一样&#xff0c;速度挺快&#xff0c;可登陆&#xff0c;可提交。 1、查看当前的代理&#xff1a; git config --global --get htt…...

SD卡与emmc的异同

eMMC与SD卡的异同&#xff1a; 物理尺寸和接口&#xff1a; eMMC&#xff1a;eMMC是一种嵌入式存储解决方案&#xff0c;通常采用BGA&#xff08;Ball Grid Array&#xff09;封装&#xff0c;焊接在电路板上。它没有标准的物理尺寸&#xff0c;而是以芯片的形式存在。SD卡&…...

机器学习笔记 - 3D 对象跟踪极简概述

一、简述 大多数对象跟踪应用程序都是 2D 的。但现实世界是 3D 的,无论您是跟踪汽车、人、直升机、导弹,还是进行增强现实,您都需要使用 3D。在 CVPR 2022(计算机视觉和模式识别)会议上,已经出现了大量3D目标检测论文。 二、什么是 3D 对象跟踪? 对象跟踪是指随着时间的…...

《机器学习----简单的分类器》第二章、朴素贝叶斯,项目:使用特征值给语句打标签

贝叶斯分类器 1,朴素贝叶斯算法1. 朴素贝叶斯算法、2. 算法思路3. 贝叶斯定理4.特征的选用的要求和处理 2&#xff0c;算法应用1 文本分类2 垃圾邮件过滤3 情感分析 3. 朴素贝叶斯的优缺点1. 优点2. 缺点 项目实践1&#xff0c;算法流程2&#xff0c;具体实现 1,朴素贝叶斯算法…...

01. 汇编LED驱动实验

01. 汇编LED驱动实验 汇编原理分析为什么要学习Cortex—A汇编STM32IO初始化流程IMX6UL初始化流程 汇编基础处理器内部数据传输指令存储器访问指令 编写驱动编译程序烧写bin文件 汇编原理分析 为什么要学习Cortex—A汇编 需要用汇编初始化一些SOC外设使用汇编初始化DDR&#x…...

Hadoop3教程(二十):MapReduce的工作机制总结

文章目录 &#xff08;109&#xff09;MapTask工作机制&#xff08;110&#xff09;ReduceTask工作机制&并行度ReduceTask工作机制MapTask和ReduceTask的并行度决定机制 &#xff08;122&#xff09;MapReduce开发总结参考文献 &#xff08;109&#xff09;MapTask工作机制…...

浅谈AI大模型技术:概念、发展和应用

AI大模型技术是指使用超大规模的深度学习模型来解决各种复杂的人工智能问题&#xff0c;如自然语言处理、计算机视觉、多模态交互等。AI大模型技术具有强大的学习能力和泛化能力&#xff0c;可以在多种任务上取得优异的性能&#xff0c;但也面临着计算、存储、通信等方面的挑战…...

【Leetcode】212.单词搜索II(Hard)

一、题目 1、题目描述 给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二维网格上的单词 。 单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中…...

146.LRU缓存

双向链表哈希表 class LRUCache { public://1、定义双向链表结构、容量、哈希表等LRU数据成员struct Node{int key,value;Node *left,*right;Node(int _key,int _value):key(_key),value(_value),left(NULL),right(NULL){}}*L,*R;int n;unordered_map<int,Node*> ump;//…...

使用transformers过程中出现的bug

1. The following model_kwargs are not used by the model: [encoder_hidden_states, encoder_attention_mask] (note: typos in the generate arguments will also show up in this list) 使用text_decoder就出现上述错误&#xff0c;这是由于transformers版本不兼容导致的 …...

Hadoop3教程(二十二):Yarn的基础架构与工作流程

文章目录 &#xff08;126&#xff09;基础架构&#xff08;127&#xff09;YARN的工作机制&#xff08;128&#xff09;作业全流程参考文献 &#xff08;126&#xff09;基础架构 之前基本介绍完了Hadoop的几个核心组件&#xff0c;接下来可以思考下&#xff0c;在MR程序运行…...

离线 notepad++ 添加到右键菜单

复制下面代码&#xff0c;修改文件后缀名为&#xff1a;reg Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\NotePad] "Notepad" "Icon""D:\\Notepad\\notepad.exe,0"[HKEY_CLASSES_ROOT\*\shell\NotePad\Command] "D:\…...

怎么让英文大语言模型支持中文?--构建中文tokenization--继续预训练--指令微调

1 构建中文tokenization 参考链接&#xff1a;https://zhuanlan.zhihu.com/p/639144223 1.1 为什么需要 构建中文tokenization&#xff1f; 原始的llama模型对中文的支持不太友好&#xff0c;接下来本文将讲解如何去扩充vocab里面的词以对中文进行token化。 1.2 如何对 原始数…...

笙默考试管理系统-MyExamTest----codemirror(35)

笙默考试管理系统-MyExamTest----codemirror&#xff08;35&#xff09; 目录 一、 笙默考试管理系统-MyExamTest 二、 笙默考试管理系统-MyExamTest 三、 笙默考试管理系统-MyExamTest 四、 笙默考试管理系统-MyExamTest 五、 笙默考试管理系统-MyExamTest 笙默考试…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

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

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

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...