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

算法 Hw9

Hw 9

  • 1 Scheduling with profits and deadlines
    • 1
    • 2
    • 3
    • 4
    • 5
  • 2 Parallel machine
    • 1
    • 2
    • 3
    • 4

1 Scheduling with profits and deadlines

1

决策问题表述:

给定一个利润值 P P P,是否存在一个任务调度方案使得完成所有任务的总利润至少为 P P P


2

在 NP 类中:
给定一个任务调度方案,可以在多项式时间内验证该方案的总利润是否至少为 P P P。验证过程包括检查每个任务是否在截止日期前完成,并计算总利润。因此,该问题在 NP 类中。

对于 NP 完全性:
- 给定一个 0/1 背包问题实例,其中有 n n n 个物品,每个物品有一个重量 w i w_i wi 和价值 v i v_i vi,以及一个总重量限制 W W W

  • 对应于调度问题中的每个任务 a j a_j aj,设置其处理时间 t j = w i t_j = w_i tj=wi,利润 p j = v i p_j = v_i pj=vi,并设置截止日期 d j = W d_j = W dj=W,保证任务必须在总时间 W W W 内完成。
  • 利润值 P P P 设为背包问题中的价值总和的要求。

通过归约,若能在调度问题中找到一个利润至少为 P P P 的方案,则在 0/1 背包问题中可以找到一个总价值至少为 P P P 且总重量不超过 W W W 的物品选择方案。因此,调度问题的决策版本是 NP 完全的。


3

  • 状态定义:设 d p [ t ] [ k ] dp[t][k] dp[t][k] 表示在总时间 t t t 内,选择前 k k k 个任务能获得的最大利润。

  • 状态转移方程:
    对于每个任务 a j a_j aj,有两种选择:

    • 不选择任务 a j a_j aj d p [ t ] [ k ] = d p [ t ] [ k − 1 ] dp[t][k] = dp[t][k-1] dp[t][k]=dp[t][k1]
    • 选择任务 a j a_j aj(前提是 t ≥ t j t \geq t_j ttj t ≤ d j t \leq d_j tdj): d p [ t ] [ k ] = max ⁡ ( d p [ t ] [ k − 1 ] , d p [ t − t j ] [ k − 1 ] + p j ) dp[t][k] = \max(dp[t][k-1], dp[t-t_j][k-1] + p_j) dp[t][k]=max(dp[t][k1],dp[ttj][k1]+pj)
  • 初始状态:

    • d p [ 0 ] [ 0 ] = 0 dp[0][0] = 0 dp[0][0]=0,表示没有时间且没有任务时的利润为 0。
  • 算法步骤:

    • 初始化 d p dp dp 数组为 0。
    • 遍历所有任务,根据上述状态转移方程更新 d p dp dp 数组。
    • 最终检查 d p [ T ] [ n ] dp[T][n] dp[T][n] 是否大于等于 P P P,其中 T T T 是计算机的总时间。

4

  • 状态定义:设 d p [ t ] dp[t] dp[t] 表示在总时间 t t t 内能获得的最大利润。

  • 状态转移方程:
    对于每个任务 a j a_j aj,有两种选择:

    • 不选择任务 a j a_j aj d p [ t ] = d p [ t ] dp[t] = dp[t] dp[t]=dp[t]
    • 选择任务 a j a_j aj(前提是 t ≥ t j t \geq t_j ttj t ≤ d j t \leq d_j tdj): d p [ t ] = max ⁡ ( d p [ t ] , d p [ t − t j ] + p j ) dp[t] = \max(dp[t], dp[t-t_j] + p_j) dp[t]=max(dp[t],dp[ttj]+pj)
  • 初始状态:

    • d p [ 0 ] = 0 dp[0] = 0 dp[0]=0,表示没有时间时的利润为 0。
  • 算法步骤:

    • 初始化 d p dp dp 数组为 0。
    • 遍历所有任务,根据上述状态转移方程更新 d p dp dp 数组。
    • 最终 d p [ T ] dp[T] dp[T] 即为最大利润,其中 T T T 是计算机的总时间。

5

由于上述动态规划算法是一个精确算法(在多项式时间内找到最优解),因此它的近似比为 1,即它能够找到最优解。


2 Parallel machine

1

考虑所有工作中处理时间最长的工作 J k J_k Jk,其处理时间为 p k = max ⁡ { p j : 1 ≤ j ≤ n } p_k = \max\{p_j : 1 \leq j \leq n\} pk=max{pj:1jn}

由于该工作必须在某台机器上连续运行 p k p_k pk 时间单位,且在此期间不能有其他工作在同一台机器上运行,因此该工作的完工时间至少为 p k p_k pk

因此,最优完工时间 C max ∗ C^*_{\text{max}} Cmax 必须至少为 p k p_k pk,即 C max ∗ ≥ max ⁡ { p k : 1 ≤ k ≤ n } C^*_{\text{max}} \geq \max\{p_k : 1 \leq k \leq n\} Cmaxmax{pk:1kn}


2

设所有工作的总处理时间为 P = ∑ k = 1 n p k P = \sum_{k=1}^{n} p_k P=k=1npk

对于最优调度,每台机器在总时间 C max ∗ C^*_{\text{max}} Cmax 内处理一部分工作。

由于共有 m m m 台机器,总的工作负载 P P P 必须分配给这 m m m 台机器。因此,平均每台机器的负载为 P m \frac{P}{m} mP

在最优调度中,任意机器的完工时间不能少于其分配到的工作负载时间,即最优完工时间 C max ∗ C^*_{\text{max}} Cmax 不能小于平均机器负载 P m \frac{P}{m} mP,即 C max ∗ ≥ 1 m ∑ k = 1 n p k C^*_{\text{max}} \geq \frac{1}{m} \sum_{k=1}^{n} p_k Cmaxm1k=1npk


3

def GreedyParallelScheduling(jobs, m):# jobs 是一个由元组 (p_k, job_id) 组成的作业列表# m 是机器的数量# 初始化了一个大小为m的空列表schedules,# 用于记录每台机器分配的作业schedules = [[] for _ in range(m)]# 初始化了一个大小为m的数组machine_completion_times,# 用于记录每台机器的完工时间,初始值为0machine_completion_times = [0] * m# 对作业列表按照处理时间的非递增顺序进行排序jobs.sort(reverse=True, key=lambda x: x[0])# 对每个已排序的作业进行调度for (p_k, job_id) in jobs:# 找到完工时间最小的机器 Mimin_machine = machine_completion_times.index(min(machine_completion_times))# 将作业分配给机器 Mischedules[min_machine].append(job_id)# 更新机器 Mi 的完工时间,增加该作业的处理时间machine_completion_times[min_machine] += p_kreturn schedules

运行时间:

  • 初始化和读取输入需要 O ( n ) O(n) O(n) 时间。
  • 对作业按处理时间排序需要 O ( n log ⁡ n ) O(n \log n) O(nlogn) 时间。
  • 遍历每个作业并找到具有最小结束时间的机器需要 O ( n log ⁡ m ) O(n \log m) O(nlogm) 时间,因为可以使用最小堆来跟踪机器的结束时间。

总体运行时间为 O ( n log ⁡ n + n log ⁡ m ) = O ( n log ⁡ n ) O(n \log n + n \log m) = O(n \log n) O(nlogn+nlogm)=O(nlogn),因为通常情况下 n ≥ m n \geq m nm


4

设所有工作的总处理时间为 P = ∑ k = 1 n p k P = \sum_{k=1}^{n} p_k P=k=1npk,处理时间最长的工作为 p max = max ⁡ { p k : 1 ≤ k ≤ n } p_{\text{max}} = \max\{p_k : 1 \leq k \leq n\} pmax=max{pk:1kn}

在贪心算法中,任何时刻将未分配的工作分配给当前空闲时间最少的机器,这种策略确保每台机器的负载是尽可能均衡的。

假设最坏情况下某台机器上的负载时间为 L L L,即 L ≤ P m + p max L \leq \frac{P}{m} + p_{\text{max}} LmP+pmax
其中, P m \frac{P}{m} mP 是平均每台机器分配到的负载时间, p m a x p_{max} pmax 是任何单个工作可能增加的最大负载时间。

因此,贪心算法的完工时间 C m a x C_{max} Cmax 满足
C max ≤ 1 m ∑ k = 1 n p k + max ⁡ { p k : 1 ≤ k ≤ n } C_{\text{max}} \leq \frac{1}{m} \sum_{k=1}^{n} p_k + \max\{p_k : 1 \leq k \leq n\} Cmaxm1k=1npk+max{pk:1kn}

由于最优完工时间 C m a x ∗ C^*_{max} Cmax 至少为这两个量中的最大值,即:
C m a x ∗ ≥ max ⁡ ( 1 m ∑ k = 1 n p k , max ⁡ { p k : 1 ≤ k ≤ n } ) C^*_{max} \geq \max \left(\frac{1}{m} \sum_{k=1}^{n} p_k, \max\{p_k : 1 \leq k \leq n\}\right) Cmaxmax(m1k=1npk,max{pk:1kn})

结合以上两个不等式,可得
C m a x ≤ 2 C m a x ∗ C_{max} \leq 2C^*_{max} Cmax2Cmax

因此,贪心算法是一个多项式时间的 2-近似算法。


相关文章:

算法 Hw9

Hw 9 1 Scheduling with profits and deadlines12345 2 Parallel machine1234 1 Scheduling with profits and deadlines 1 决策问题表述: 给定一个利润值 P P P,是否存在一个任务调度方案使得完成所有任务的总利润至少为 P P P 2 在 NP 类中&…...

前端JS必用工具【js-tool-big-box】学习,字符串字母大小写转换的方法使用

这一小节,我们说一下 js-tool-big-box 工具库中,字符串字母大小写转换的使用。请注意:不是说单纯的把字符串转为大写,或者小写。关注 js-tool-big-box 的小伙伴可能知道,我们并没有把一些特别基础的,JS原生…...

Zookeeper:分布式系统中的协调者

Zookeeper:分布式系统中的协调者 前言:引言Zookeeper是什么? 基本概念Zookeeper 数据模型Znode 类型会话Watcher 应用场景分布式锁配置维护组服务名字服务 典型应用场景数据发布/订阅负载均衡命名服务分布式协调/通知集群管理Master选举 工作…...

如何使用代理IP进行数据抓取,PHP爬虫抓取京东商品数据

使用代理IP进行数据抓取通常是为了绕过IP封锁、提高抓取效率或保护你的真实IP地址。在PHP中,你可以使用cURL库来发送HTTP请求,并通过设置cURL选项来使用代理IP。 以下是一个基本的步骤说明,展示如何使用PHP和cURL库结合代理IP来抓取京东商品…...

一口气安装【Python】教程

浏览器搜索python,或者直接跳转网址。 https://www.python.orghttps://www.python.org/ 找到想下载的版本 根据自己电脑下载相应的版本 自定义安装 下一步 修改路径,然后点击安装 等待一会,喝个饮料 点击关闭 安装成功 安装结束...

华为HCIP Datacom H12-821 卷13

1.多选题 以下关于二层漫游和三层漫游的描述,以下说法正确的是? A、如果 STA 漫游时前后关联的 VLAN ID 相同则一定属于二层漫游 B、二层漫游是指客户端在同一子网内漫游 C、三层漫游是指客户端在不同子网间漫游 D、三层漫游前后 STA 关联的 AP 服务集上的 VL AN 必须相…...

基于SSM的酒店客房管理系统

基于SSM的酒店客房管理系统 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅获取项目下载方式🍅 链接点击直达:下载…...

【数据结构与算法】最短路径,Floyd算法,Dijkstra算法 详解

Floyd算法 for (int k 0; k < n; k) {for (int i 0; i < n; i) {for (int j 0; j < n; j) {if (d[i][k] ! INF && d[k][j] ! INF) {d[i][j] min(d[i][j], d[i][k] d[k][j]);}}} }Dijkstra算法&#xff08;基于最小堆&#xff09; void dijkstra(int st…...

PHP中如何进行网络爬虫和数据抓取?

随着互联网时代的到来&#xff0c;网络数据的爬取与抓取已成为许多人的日常工作。在支持网页开发的程序语言中&#xff0c;php以其可扩展性和易上手的特点&#xff0c;成为了网络爬虫和数据抓取的热门选项。本文将从以下几个方面介绍php中如何进行网络爬虫和数据抓取。 一、HT…...

【Hadoop集群搭建】实验3:JDK安装及配置、Hadoop本地模式部署及测试

1. 安装 SSH 工具 SSH Secure Shell Client 传输软件 FinalShell(推荐使用) 1.1使用SSH工具将JDK安装包上传至虚拟主机hadoop01, hadoop02, hadoop03&#xff0c;sogou500w 数据上传至 hadoop01。 a. 在虚拟主机/usr 目录下创建文件夹 java&#xff0c;JDK 上传至此目录&…...

分布式锁在Spring Boot应用中的优雅实现

在现代微服务架构中&#xff0c;分布式锁是一种常用的技术手段&#xff0c;用于确保在分布式系统中&#xff0c;同一时间只有一个服务实例能够执行某个特定的操作。这对于防止并发问题、保证数据一致性至关重要。在Spring Boot应用中&#xff0c;我们可以通过自定义注解和切面的…...

常用框架-Spring Boot

常用框架-Spring Boot 1、Spring Boot是什么?2、为什么要使用Spring Boot?3、Spring Boot的核心注解是哪个?它主要由哪几个注解组成的?4、有哪些运行Spring Boot的方式?5、如何理解 Spring Boot 中的Starters?6、有哪些常见的Starters?7、如何在Spring Boot启动的时候运…...

AttributeError: module ‘cv2‘ has no attribute ‘face‘

Traceback (most recent call last): File "D:\AI_37\pythonProject7\day23\课堂代码\day23\07-人脸识别.py", line 4, in <module> recognizer cv2.face.LBPHFaceRecognizer_create() ^^^^^^^^ AttributeError: module cv2 has no at…...

不管你是普本还是双一流,建议你一定要尝试一下学习GIS开发

毕业季&#xff0c;很多企业的秋招和暑期实习已经开始了&#xff0c;在这个24秋招和25考研并列进行的毕业季&#xff0c;GIS专业的同学&#xff0c;做好自己的职业规划显得十分重要。 WebGIS开发&#xff0c;近年来成为了3S及相关专业的学生备受关注的热门选择。 不论是本科毕…...

OurBMC大咖说丨第5期:BMC开发中的非标准化问题探讨

栏目介绍&#xff1a;"OurBMC大咖说" 是由 OurBMC 社区精心策划的线上讲座栏目&#xff0c;邀请 BMC 相关领域大咖共同探讨 BMC 全栈技术的发展趋势、挑战和机遇。无论你是初学者还是资深从业者&#xff0c;"OurBMC大咖说" 都将为你提供一个宝贵的学习和交…...

空调制冷剂泄漏引发健康隐患,冷媒传感器实时监测至关重要

随着夏季的脚步逐渐临近&#xff0c;气温逐渐攀升&#xff0c;空调成为了许多家庭和企业必不可少的降温设备。然而&#xff0c;近年来多起因空调制冷剂泄漏导致的健康问题和安全事故&#xff0c;让人们开始重新审视空调使用安全的重要性。其中&#xff0c;冷媒传感器的实时监测…...

开源TinyFSM状态机适用于嵌入式工业平台吗?

文章目录 引言基于传统 C 实现的状态机TinyFSM 实现的对比现代 C 实现的状态机性能对比TinyFSM 性能测试传统 C 性能测试现代 C 性能测试 工业Misra C编程标准TinyFSM 的优缺点分析结论 引言 TinyFSM是一个为C设计的轻量级有限状态机开源库库。 在嵌入式系统开发中&#xff0c…...

EE trade:利弗莫尔三步建仓法

在股市投资领域&#xff0c;利弗莫尔这个名字代表着无数的智慧和经历。他的三步建仓法成为了投资者们趋之若鹜的学习对象。本文将详细解析利弗莫尔的著名买入法&#xff0c;通过分步进攻方式&#xff0c;有效掌控市场并实现盈利。 一、利弗莫尔的三步建仓法详解 利弗莫尔三步…...

Java中Callable的应用

在Java中&#xff0c;Callable接口是一种用于并发编程的接口&#xff0c;它与Runnable类似&#xff0c;但有一些重要的区别和优势。Callable接口提供了一种在多线程环境下执行任务并返回结果的方法。以下是一些Callable接口的常见应用场景和使用示例&#xff1a; Callable vs.…...

测试卡无法仪表注册问题分析

1、问题描述 00101测试卡无法注册LTE网络&#xff0c;modemlog中发现终端未发起Attach请求&#xff0c;对比正常注册非正常注册的版本&#xff0c;发现正常的多出了ims apn。可以通过ATCGDCONT?来查询modem APN参数。 2、问题分析 目前Modem是一套&#xff0c;没有相关修改。因…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

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

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

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...