贪心算法(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);}

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

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

相关文章

网络编程的学习初篇

网络原理初始 网络原理和网络编程[重要] 网络能够跨主机通信! 我们未来工作,很可能是成为后端开发工程师,写服务器,和客户端通信,肯定会涉及到网络. 网络初始 计算机网络的由来 ~~ 计算机网络这是计科相关专业最核心的专业课!!! 计算机是咋来的??最初是用来计算弹道导弹的轨…

Kubernetes技术与架构-Ingress Controller

Ingress Controller控制器是实现Ingress对象的定义的组件&#xff0c;也即网关&#xff0c;负责Kubernetes集群内流量的分发&#xff0c;Kubernetes可以运行多个Ingress Controller控制器实例&#xff0c;不同的Ingress定义可以使用不同的Ingress Controller控制器实现&#xf…

搞个微信小程序002:个人信息

新建一个用于&#xff0c;和001中一样&#xff0c;然后&#xff0c;就改掉两个文件&#xff1a; index.wxml: <view><!-- 头像区域 --><view class"top"><view class"user-img"><image src"/images/tx.png"><…

PostgreSQL 插件 CREATE EXTENSION 原理

PostgreSQL 提供了丰富的数据库内核编程接口&#xff0c;允许开发者在不修改任何 Postgres 核心代码的情况下以插件的形式将自己的代码融入内核&#xff0c;扩展数据库功能。本文探究了 PostgreSQL 插件的一般源码组成&#xff0c;梳理插件的源码内容和实现方式&#xff1b;并介…

mybatis写sql

批量查询 <select id"getPreIds" resultType"java.lang.String"parameterType"java.util.List">SELECT pre_batch_id FROM public.mine_data_quality_check_record WHERE deleted0<if test"list ! null">AND pre_batch…

codeshell安装配置

codeshell安装配置 1 注意事项1.1 Python版本问题 2 codeshell环境搭建2.1 codeshell使用软件各版本2.2 软件下载2.3 codeshell使用环境安装2.3.1 python-3.10.9-amd64.exe安装2.3.2 Anaconda3-2022.10-Windows-x86_64.exe安装2.3.3 创建环境2.3.4 Pytorch安装2.3.5 transforme…

C++初阶 入门(2)

目录 一、缺省函数 1.1什么是缺省函数 1.2为什么要有缺省函数 1.3使用缺省函数 1.4测试代码 二、函数重载 2.1什么是函数重载 2.2为什么要有函数重载 2.3什么情况构成函数重载 2.4函数重载例子及代码 三、引用 3.1什么是引用 3.2如何引用 ​3.3常引用(可略过) 3…

CCF CSP认证历年题目自练Day38

题目 试题编号&#xff1a; 201409-3 试题名称&#xff1a; 字符串匹配 时间限制&#xff1a; 1.0s 内存限制&#xff1a; 256.0MB 问题描述&#xff1a; 问题描述   给出一个字符串和多行文字&#xff0c;在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感…

酒类商城小程序怎么做

随着互联网的快速发展&#xff0c;线上购物越来越普及。酒类商品也慢慢转向线上销售&#xff0c;如何搭建一个属于自己的酒类小程序商城呢&#xff1f;下面就让我们一起来看看吧&#xff01; 一、登录乔拓云平台 首先&#xff0c;我们需要进入乔拓云平台的后台&#xff0c;点击…

《向量数据库》——Zilliz X Dify.AI ,快速打造知识库 AI 应用

Zilliz 大模型生态矩阵再迎新伙伴!近日,Zilliz 和 Dify.AI 达成合作,Zilliz 旗下的产品 Zilliz Cloud、Milvus 与开源 LLMOps 平台 Dify 社区版进行了深度集成。 01. Zilliz Cloud v.s. Dify Dify 作为开源的 LLMs App 技术栈,在此前已支持丰富多元的大型语言模型的接入,…

【React Router】React Router学习笔记

React Router学习笔记 React Router1.什么是React Router?2.为什么要用React Router?3.基础3.1 路由配置3.2 路由匹配原理3.3 History3.3.1 browerHistory3.3.2 hashHistory3.3.3 createMemoryHistory3.3.4 实现示例 3.4 默认路由(IndexRoute)与IndexLink3.4.1 IndexRoute3.4…

[SQL开发笔记]WHERE子句 : 用于提取满足指定条件的记录

SELECT DISTINCT语句用户返回列表的唯一值&#xff1a;这是一个很特定的条件&#xff0c;假设我需要考虑很多中限制条件进行查询呢&#xff1f;这时我们就可以使用WHERE子句进行条件的限定 一、功能描述&#xff1a; WHERE子句用于提取满足指定条件的记录&#xff1b; 二、WH…

报错解决:libcudart.so和libprotobuf.so链接库未找到

报错解决&#xff1a;libcudart.so和libprotobuf.so链接库未找到 libcudart.so链接库未找到原因解决方法 libprotobuf.so链接库未找到原因解决方法 此博客介绍了博主在编译软件包时遇到的两个报错&#xff0c;主要是libcudart和libprotobuf两个动态链接库未找到的问题&#xff…

Nginx安装配置项目部署然后加SSL

个人操作笔记记录 第一步&#xff1a;把 nginx 的源码包nginx-1.8.0.tar.gz上传到 linux 系统 第二步&#xff1a;解压缩 tar zxvf nginx-1.8.0.tar.gz 第三步&#xff1a;进入nginx-1.8.0目录 使用 configure 命令创建一 makeFile 文件。 直接复制过去运行 ./configur…

【RocketMQ系列十二】RocketMQ集群核心概念之主从复制生产者负载均衡策略消费者负载均衡策略

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精…

KingBase库模式表空间和客户端认证(kylin)

库、模式、表空间 数据库 数据库基集簇与数据库实例 KES集簇是由单个KES实例管理的数据库的集合KES集簇中的库使用相同的全局配置文件和监听端口、共享相关的进程和内存结构同一数据库集簇中的进程、相关的内存结构统称为实例 数据库 数据库是一个长期存储在计算机内的、有…

【Tensorflow 2.12 简单智能商城商品推荐系统搭建】

Tensorflow 2.12 简单智能商城商品推荐系统搭建 前言架构数据召回排序部署调用结尾 前言 基于 Tensorflow 2.12 搭建一个简单的智能商城商品推荐系统demo~ 主要包含6个部分&#xff0c;首先是简单介绍系统架构&#xff0c;接着是训练数据收集、处理&#xff0c;然后是召回模型、…

redis分布式锁的应用

redis 作为分布式锁的东西 分布式锁的应用 redis,zk,数据库这些都可以实现分布式锁 我们今天主要基于redis实现的分布式锁&#xff0c;而且要求性能要好 基于一个小的业务场景来说&#xff0c;就比如说秒杀中的减库存&#xff0c;防止超卖这种代码就会有并发问题,比方说3个线程…

uni-app开发

uni-app 官方手册&#xff1a;uni-app官网 一&#xff1a;tarBar&#xff1a;一级导航栏&#xff0c;即 tab 切换时显示对应页。 在pages.json文件里写入如下代码&#xff1a; 此效果&#xff1a;

编译工具链 之一 基本概念、组成部分、编译过程、命名规则

编译工具链将程序源代码翻译成可以在计算机上运行的可执行程序。编译过程是由一系列的步骤组成的&#xff0c;每一个步骤都有一个对应的工具。这些工具紧密地工作在一起&#xff0c;前一个工具的输出是后一个工具的输入&#xff0c;像一根链条一样&#xff0c;我们称这一系列工…