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

贪心算法(1)--经典贪心算法

目录

一、活动安排问题

二、最优装载问题

三、分数背包问题

四、多机调度问题


一、活动安排问题

1、策略

        活动安排问题:设有n个活动的集合E={1,2,...,n},每个活动i都有一个使用该资源的起始时间s_i和一个结束时间f_i,且s_i<f_i。如果选择了活动i则它在时间区间[s_i,f_i)内占用资源,如何在有限的时间内选择最多的活动方案安排。

        解法按结束时间优先的贪心算法。

(1) 如果活动i和活动j能够相容,假设活动i在活动j之前,那么一定有f_i\leqslant s_j

(2)按照f_i序列对f_is_i同时进行排序,保证两者对应。排序可以使用快速排序、归并排序和堆排复杂度为O(nlogn)。

(3)第1个活动f_i最小,所以进入活动安排,其他如果存在s_j\geqslant f_i,则i=j,移动活动安排。

       给定一个活动序列 i,s_i,f_i的关系:

2、代码 

//活动安排
import java.util.Scanner;
public class activityarrangement {public static void main(String[] args){int n=new Scanner(System.in).nextInt();int s[]=new int[n];int f[]=new int[n];for(int i=0;i<n;i++)s[i]=new Scanner(System.in).nextInt();for(int i=0;i<n;i++)f[i]=new Scanner(System.in).nextInt();quickSort(f,s, 0, n-1);GreedySelector(s,f);}public static void GreedySelector(int s[],int f[]) {System.out.println(s[0]+" "+f[0]);int j=0;for(int i=1;i<s.length;i++){if(s[i]>=f[j]){System.out.println(s[i]+" "+f[i]);j=i;}}}

二、最优装载问题

1、策略

        有一批集装箱要装上一艘载重为c的轮船,集装箱i的重量为w_i,要求装载体积不受限制情况下,将尽可能多的集装箱装上轮船。

        利用贪心算法重量最轻的集装箱优先装载,直到轮船载重无法继续装入集装箱。

        排序方法可以使用快排、归排和堆排来降低时间复杂度。

        约束条件和目标函数如下:

        例题如下: 

2、代码 

//最优装载问题
public static void main(String []args) {int c=400;int weights[]={100,200,50,90,150,50,20,80};quickSort(weights,0,weights.length-1);System.out.println(load(weights,c));}
public static int load(int weights[],int c){int tmp=c;for(int i=0;i<weights.length;i++){if(c>weights[i]){c-=weights[i];}}return tmp-c;} 

三、分数背包问题

1、策略

        分数背包问题:在0-1背包的问题基础上,可以每个物品装一部分,即0~1背包问题,要求在有限的容量基础上,求解装有物品的最高总价值。

        策略:以单位重量价值最高的优先的贪心算法。

        建立a数组(单位重量下价值),以a数组为排序依据,同时排序a,w,v数组,计算a数组较大值优先的情况下能产生的最大总价值。

        例题如下:

2、代码

(省略排序过程)

//分数背包问题
public class dividebackage {
public static void main(String[] args){int n=3;int c=20;double w[]={18,15,10};double v[]={25,24,15};double a[]=new double[n];for(int i=0;i<n;i++)a[i]=v[i]/w[i];quickSort(a,w,v,0,w.length-1);System.out.println(maximum(a,w,v,c));} 
public static double maximum(double a[],double w[],double v[],int c){double value=0;int weight=0;for(int i=a.length-1;i>=0;i--){if((c-weight)>=w[i]){value+=v[i];weight+=w[i];}else{value+=v[i]*(c-weight)/w[i];break;}}return value;}
}

四、多机调度问题

1、概述

        多机调度问题:设有n个独立作业,由m台相同机器进行加工处理,作业i所需的处理时间为t_i,每个作业均可以在任何一台机器上加工处理,但不可间断、拆分。设计一种算法,使得n个作业在尽可能短的时间内由m台机器加工处理完成。

        策略:按任务时间较长的进行贪心算法,设定time,p,d,m,s五个数组(定义看下面代码注释),首先对time数组和p数组按任务时间降序排序(快排),调度问题为添加任务和时间推移两个阶段循环进行,直到任务不再添加,所有机器还需占用时间数为0,则退出调度问题。

        添加任务:遍历每一个机器,若当前机器m还需占用时间为0,且仍有任务i需要添加,则将任务i添加到机器m,机器m的所做任务数加一,机器m执行任务添加任务i编号。

        时间推移:时间后移一,每个任务的还需所占用时间减一,若每个机器的所占用时间都为0且没有新任务添加,则退出调度问题,返回当前时间。若存在机器i所占用时间为0,但仍有其他机器任务未结束,则机器i占用时间不再减少,避免出现负数。

        下面例题解决效果:

2、代码 

//多机调度问题
public class multimachine {public static void main(String[] args){int time[]={2,14,4,16,6,5,3};               //每个任务所占时间int p[]={1,2,3,4,5,6,7};                    //任务编号int d[]={0,0,0};                            //当前机器还需占用时间数int m[]={0,0,0};                            //每个机器执行了几个任务int s[][]=new int[d.length][time.length];   //每个机器执行了哪些任务//对时间列和任务编号进行重新排序quickSort(time,p,0,time.length-1);//输出多机调度总时间deploy(time,p,d,s,m);//输出每个机器执行了哪些任务for(int i=0;i<d.length;i++){for(int j=0;j<time.length;j++){if(s[i][j]==0)break;System.out.print(s[i][j]+" ");}System.out.println("");}} public static void deploy(int time[],int p[],int d[],int s[][],int m[]){int tot=0;int c=0;    //总作业序列顺序执行到几个while(true){//进入任务,增加每个机器的所占用时间for(int i=0;i<d.length;i++){if(d[i]==0&&c<time.length){d[i]+=time[c];s[i][m[i]++]=p[c++];}}tot+=1;int zero=0;//时间推移加一,减少每个机器的所占用时间for(int i=0;i<d.length;i++){if(d[i]==0)break;d[i]--;zero+=d[i];}//若每个机器都为0,且没有任务继续添加,则终止调度if(zero==0)break;}System.out.println(tot);}

相关文章:

贪心算法(1)--经典贪心算法

目录 一、活动安排问题 二、最优装载问题 三、分数背包问题 四、多机调度问题 一、活动安排问题 1、策略 活动安排问题&#xff1a;设有n个活动的集合E{1,2,...,n}&#xff0c;每个活动i都有一个使用该资源的起始时间和一个结束时间&#xff0c;且。如果选择了活动i则它在…...

Nginx负载均衡和备份和故障转移

如果你想要两台 Nginx 服务器配置访问同一个链接&#xff0c;通常意味着你可能想要以下几种配置&#xff1a; 负载均衡&#xff1a;两台 Nginx 服务器都工作&#xff0c;当访问者请求资源时&#xff0c;流量会在这两台服务器之间进行均衡分配。备份和故障转移&#xff1a;其中…...

Android-Framework 三方应用默认权限都不弹窗

代码位置&#xff1a;frameworks/base/services/core/java/com/android/server/pm/PackageManagerService.java -1853,10 1853,10 public class PackageManagerService extends IPackageManager.StubmPermissionCallback);}- final String packageName res.pkg.application…...

TX Text Control.NET For WPF 32.0 Crack

TX Text Control 支持VISUAL STUDIO 2022、.NET 5 和 .NET 6 支持 .NET WPF 应用程序的文档处理 将文档编辑、创建和 PDF 生成添加到您的 WPF 应用程序中。 视窗用户界面 功能齐全的文档编辑器 TX Text Control 是一款完全可编程的丰富编辑控件&#xff0c;它在专为 Visual Stu…...

使用Go语言测试Redis性能

1. 前言 Redis是一个高性能的键值存储数据库&#xff0c;常用于缓存、队列、排行榜等场景。在实际应用中&#xff0c;我们需要对Redis的性能进行测试&#xff0c;以便了解其在不同场景下的表现。本文将介绍如何使用Go语言测试Redis的性能。 2. 环境准备 在开始测试前&#x…...

【Javascript】运算符(赋值,算术,自增,自减)

目录 赋值 算术 单个变量&#xff1a; 多个变量&#xff1a; 在字符串&#xff0c;数组中充当连接符 自符串与字符串 数组与数组 数组与字符串 自增与自减 前置 自增 自减 后置 自增 自减 赋值 var a 1;算术 单个变量&#xff1a; var a 1;a 1;console.l…...

Redis数据类型——list类型数据的扩展操作

1.list阻塞式数据获取 2.list类型数据业务场景...

[论文笔记]NEZHA

引言 今天带来华为诺亚方舟实验室提出的论文NEZHA,题目是 针对中文中文语言理解神经网络上下文表示(NEural contextualiZed representation for CHinese lAnguage understanding),为了拼出哪吒。 预训练语言模型由于具有通过对大型语料库进行预训练来捕获文本中深层上下文信…...

【Linux】认识协议

目录 一、应用层二、协议三、序列化和反序列化 一、应用层 之前的socket编程&#xff0c;都是在通过系统调用层面&#xff0c;如今我们来向上打通计算机网络。认识应用层的协议和序列化与反序列化 我们程序员写的一个个解决我们实际问题, 满足我们日常需求的网络程序, 都是在应…...

Hadoop3教程(三十四):(生产调优篇)MapReduce生产经验汇总

文章目录 &#xff08;164&#xff09;MR跑得慢的原因&#xff08;165&#xff09;MR常用调优参数Map阶段Reduce阶段 &#xff08;166&#xff09;MR数据倾斜问题参考文献 &#xff08;164&#xff09;MR跑得慢的原因 MR程序执行效率的瓶颈&#xff0c;或者说当你觉得你的MR程…...

Unity⭐️Win和Mac安卓打包环境配置

文章目录 🟥 配置Android SDK1️⃣ 配置 SDK Platforms2️⃣ 配置 SDK Tools🎁 Android SDK Build-Tools🎁 Android SDK Command-line Tools(latest)🎁 Android SDK Tools(Obsolete)🟧 配置NDK🟩 配置JDK前情提示: 此方法适用于Windows/Mac 在配置时注意开启 🪜 …...

STM32F4XX之串口

一、标准串口&#xff08;UART&#xff09;介绍 1、通信协议相关概念 1.1同步通信和异步通信 (1)同步通信&#xff1a;两个器件之间共用一个时钟线&#xff0c;要发送的数据在时钟的作用下一位一位发送出去。 &#xff08;2&#xff09;异步通信&#xff1a;指两个器件之间没…...

【J-Long Group Limited】申请1500万美元纳斯达克IPO上市

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 猛兽财经获悉&#xff0c;总部位于中国香港的J-Long Group Limited&#xff08;简称&#xff1a;J-Long&#xff09;近期已向美国证券交易委员会&#xff08;SEC&#xff09;提交招股书&#xff0c;申请在纳斯达克IPO上市&…...

上传文件到google drive

参考&#xff1a;使用 Python 将文件上传到 Google 云端硬盘_迹忆客 第 1 步&#xff1a;Google API Playground 我们可以通过搜索 Google 找到更多关于 Google API Playground 的信息。 我们必须单击第一个链接才能继续前进。 选择第一个链接后&#xff0c;我们会自动进入下一…...

用VLOOKUP快速合并两个表格

一、前言 上周五微信收到运营提过来的需求&#xff0c;第一句话&#xff1a;帮我提取一下1号门店的库存数据&#xff0c;马上登录系统下载一份库存数据给到他然后专心读代码&#xff0c;过一会微信第二句话&#xff1a;帮我提取一下1号门店商品半年/一年的销量数据&#xff0c…...

Vue ref属性

Vue中的ref属性可以用来对HTML元素或者是对组件进行唯一标识。 一、设置ref属性 只需要在元素或者是组件后跟上如下语法即可&#xff1a; ref"标识名" 二、获取元素或对象 我们可以用如下方法获取我们设置ref的元素或组件&#xff1a; this.$refs.标识名 第一个输…...

【python入门】函数,类和对象

【大家好&#xff0c;我是爱干饭的猿&#xff0c;本文重点介绍python入门的函数&#xff0c;高阶函数&#xff0c;python中的类和对象&#xff0c;模块的作用等。 后续会继续分享其他重要知识点总结&#xff0c;如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff0c;关…...

alibaba.fastjson的使用(二)-- jar包导入

目录 1. 在pom文件中引入依赖: 2.fastjsonv2的使用: 1. 在pom文件中引入依赖: <dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>2.0.14</version> </dependency>2.fastjsonv2的使用…...

A_搜索(A Star)算法

A*搜索(A Star) 不同于盲目搜索&#xff0c;A算法是一种启发式算法(Heuristic Algorithm)。 上文提到&#xff0c;盲目搜索对于所有要搜索的状态结点都是一视同仁的&#xff0c;因此在每次搜索一个状态时&#xff0c;盲目搜索并不会考虑这个状态到底是有利于趋向目标的&#x…...

Tinywebserve学习之linux 用户态内核态

一.CPU指令集权限 指令集是实现CPU实现软件指挥硬件执行的媒介&#xff0c;具体来说每一条汇编语句都对应了一条CPU指令&#xff0c;而非常多的CPU指令再一起组成一个甚至多个集合&#xff0c;指令的集合叫CPU指令集&#xff1b; 因为CPU指令集可以操纵硬件&#xff0c;会造成…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...