2021华为软挑初探——代码实现

article/2025/9/15 16:19:28

其他工作：

2021华为软挑部分答疑——哪些你有错却总是找不到的地方，我来带你找啦（含标准输入代码）

2021华为软挑再探——代码实现

这几天华为软挑好多人也是做的热火朝天，作为一个渣渣小孙也来探探，不探不知道一探吓一跳，天呐，自己菜的可怕。试了多次都还停留在超时上，😫😫😫！不过也算有一点小收获，

今年华为软挑的题是一个云上资源规划与调度问题，问题的主要是购买服务器和虚拟机部署在哪个服务器上以及虚拟机的迁移问题。大致就是这样：

这篇文章第一次写难免存在写问题，于是，小孙又再探了：

我的大致思路是来自这几篇论文：

《多目标一维装箱问题模型算法研究》

《基于三支决策的虚拟机节能迁徙策略》

《基于重力装载的自适应随机算法求解多箱型三维装箱问题》

《基于自适应虚拟机迁移的云资源调度机制》

今天写了个能解出结果的代码，代码如下：

import sys
import os
import re
import random
import numpy as np
import copy
import timeclass GA:def __init__(self):self.P_c=0.8            #交叉概率self.P_m=0.8            #变异概率self.Pop_Size=10        #种群大小self.Iter=10            #迭代次数self.P_z=0.6            #选择概率self.P_w=0.2def Sever_Select(self,K,Sever):V=copy.copy(K)Selected_Sever = []Select = random.choice(Sever)Select_i = Sever_Machine(Select)while V != []:Select_V =random.choice(V)result = Select_i.Judge_whether_to_insert(Select_V)if result == True:  # 随机配置V.remove(Select_V)if V==[]:Selected_Sever.append(Select_i)breakif result == False:for i in range(len(V)):result = Select_i.Judge_whether_to_insert(V[i])if result == True:V.remove(V[i])breakif result == False and i >= len(V) - 1:Selected_Sever.append(Select_i)Select = random.choice(Sever)Select_i = Sever_Machine(Select)return Selected_Severdef Encode(self,V,Sever):Sev_Mac=[]for i in range(self.Pop_Size):Sev_Mac.append(self.Sever_Select(V,Sever))return Sev_Macdef Fitness(self,Sev_Mac,use_Day):Fit=[]for i in range(len(Sev_Mac)):Fit_i=0if Sev_Mac[i]==None:print(i)passelse:for j in range(len(Sev_Mac[i])):Fit_i+=Sev_Mac[i][j].Hardware_cost+use_Day*Sev_Mac[i][j].Energy_costFit.append(Fit_i)return Fitdef Crossover(self,CHS1,CHS2):ML=min(len(CHS1),len(CHS2))R=random.randint(1,ML-1)T0=[i for i in range(ML)]random.shuffle(T0)T0=T0[0:R]for j in T0:Load_1=CHS1[j].Node_Situation()Load_2=CHS2[j].Node_Situation()Sev = [CHS2[j].Model,CHS2[j].CPU_cores,CHS2[j].Memory_Size,CHS2[j].Hardware_cost,CHS2[j].Energy_cost ]if Load_1[0]<=CHS2[j].CPU_cores/2 and Load_1[1]<=CHS2[j].CPU_cores/2 and\Load_1[3]<=CHS2[j].Memory_Size/2 and Load_1[3]<=CHS2[j].Memory_Size/2 :if CHS1[j].Energy_cost>=CHS2[j].Energy_cost and CHS1[j].Hardware_cost>=CHS2[j].Hardware_cost:CHS1[j].replace_machine(Sev)else:if random.random()<self.P_z:CHS1[j].replace_machine(Sev)return CHS1def Mutation(self,CHS1,Sever):L=len(CHS1)R=random.randint(1,L-1)T0=[i_1 for i_1 in range(R)]random.shuffle(T0)T0=T0[0:R]for i in T0:Load=CHS1[i].Use_situation()Load_CPU=Load[0]Load_M=Load[1]for j in range(len(Sever)):if Sever[j][1]>=Load_CPU and Sever[j][2]>=Load_M :if CHS1[i].Hardware_cost<=Sever[j][3] and CHS1[i].Energy_cost<=Sever[j][4]:CHS1[i].replace_machine(Sever[j])else:if random.random()>self.P_w:CHS1[i].replace_machine(Sever[j])breakreturn CHS1def Select(self,Fit_value,POP_SIZE):Fit=[]for i in range(len(Fit_value)):fit=1/Fit_value[i]Fit.append(fit)Fit=np.array(Fit)idx = np.random.choice(np.arange(len(Fit_value)), size=len(Fit_value), replace=True,p=(Fit) / (Fit.sum()))return idxdef main(self,V,Sever,use_Day):CHS=self.Encode(V,Sever)Best=[]Best_Fit_end=Nonefor i in range(self.Iter):Fit=self.Fitness(CHS,use_Day)Best_Fit=min(Fit)Best_Sev=CHS[Fit.index(Best_Fit)]if Best_Fit_end==None or Best_Fit<Best_Fit_end:Best.append(Best_Sev)Best_Fit_end=Best_FitSelect=self.Select(Fit,self.Pop_Size)CHS=[CHS[C_i] for C_i in Select]for j in range(len(CHS)):if random.random()<self.P_c:CHS2=random.choice(CHS)C=self.Crossover(CHS[j],CHS2)CHS[j]=Cfor j_1 in range(len(CHS)):if random.random()<self.P_m:M=self.Mutation(CHS[j_1],Sever)CHS[j_1]=Mreturn Best[-1]class Virtual_Machine:def __init__(self,V,user):self.Model=V[0]self.CPU_cores=V[1]self.Memory_Size=V[2]self.Deployment=V[3]self.user=0class Sever_Machine:def __init__(self,Sever):self.Model=Sever[0]                    #型号self.CPU_cores=Sever[1]            #CPU核数self.Memory_Size=Sever[2]        #内存大小self.Hardware_cost=Sever[3]    #硬件成本self.Energy_cost=Sever[4]        #能耗成本self.Node_A=[]                      #当前A节点剩余核数内存情况self.Node_B=[]                      #当前B节点剩余核数内存情况self.Both=[]self.assigned=[]self.assigned_Node=[]self.rest_CPU_A=self.CPU_cores/2self.rest_Memory_A=self.Memory_Size/2self.rest_CPU_B = self.CPU_cores/2self.rest_Memory_B = self.Memory_Size/2def add_to_Node_A(self,V):self.Node_A.append(V)self.assigned.append(V.user)self.assigned_Node.append(1)self.rest_CPU_A -= V.CPU_coresself.rest_Memory_A -= V.Memory_Sizedef add_to_Node_B(self,V):self.Node_B.append(V)self.assigned.append(V.user)self.assigned_Node.append(2)self.rest_CPU_B -= V.CPU_coresself.rest_Memory_B -= V.Memory_Sizedef add_to_both(self,V):self.Both.append(V)self.assigned.append(V.user)self.assigned_Node.append(0)self.rest_CPU_A-=V.CPU_cores/2self.rest_Memory_A-=V.Memory_Size/2self.rest_CPU_B -= V.CPU_cores / 2self.rest_Memory_B -= V.Memory_Size / 2def Judge_whether_to_insert(self,V):C=V.CPU_coresM=V.Memory_SizeA=self.rest_CPU_AB=self.rest_Memory_AC=self.rest_CPU_BD=self.rest_Memory_BK=[]if V.Deployment==1:if self.rest_CPU_A>=V.CPU_cores/2 and self.rest_CPU_B>=V.CPU_cores/2 and\self.rest_Memory_A>=V.Memory_Size/2 and self.rest_Memory_B>=V.Memory_Size/2:self.add_to_both(V)return Trueelse:return Falseif V.Deployment==0:if self.rest_CPU_A>=V.CPU_cores and self.rest_Memory_A>=V.Memory_Size :K.append(1)if self.rest_CPU_B >= V.CPU_cores and self.rest_Memory_B >=V.Memory_Size:K.append(2)if len(K)==2:if random.choice(K)==1:self.add_to_Node_A(V)else:self.add_to_Node_B(V)return Trueelif len(K)==1:if K==1:self.add_to_Node_A(V)else:self.add_to_Node_B(V)return Trueelse:return Falsedef del_Virtual(self,V):K=self.assigned.index(V.user)M=self.assigned_Node[K]if M==0:self.rest_CPU_A += V.CPU_coresself.rest_Memory_A += V.Memory_Sizeif M==1:self.rest_CPU_B += V.CPU_coresself.rest_Memory_B += V.Memory_Sizeif M==0:self.rest_CPU_A += V.CPU_cores / 2self.rest_Memory_A += V.Memory_Size / 2self.rest_CPU_B += V.CPU_cores / 2self.rest_Memory_B += V.Memory_Size / 2self.assigned.remove(K)del self.assigned_Node[K]def Node_Situation(self):Load_CPU_A=self.CPU_cores/2-self.rest_CPU_ALoad_CPU_B=self.CPU_cores/2-self.rest_CPU_BLoad_M_A=self.Memory_Size/2-self.rest_Memory_ALoad_M_B=self.Memory_Size/2-self.rest_Memory_Breturn Load_CPU_A,Load_CPU_B,Load_M_A,Load_M_Bdef Use_situation(self):Load_CPU= self.CPU_cores  - self.rest_CPU_A-self.rest_CPU_ALoad_M = self.Memory_Size - self.rest_Memory_A- self.rest_Memory_Breturn Load_CPU,Load_Mdef replace_machine(self,Sev):self.Model = Sev[0]  # 型号self.CPU_cores = Sev[1]  # CPU核数self.Memory_Size = Sev[2]  # 内存大小self.Hardware_cost = Sev[3]  # 硬件成本self.Energy_cost = Sev[4]  # 能耗成本class daily_situation:def __init__(self,Sever,Virtual,use_Case):self.Sever=Severself.Virtual=Virtualself.use_Case=use_Caseself.days=0.2*(len(use_Case))def Sever_Select(self,K):V=copy.copy(K)Selected_Sever = []Select = random.choice(self.Sever)Select_i = Sever_Machine(Select)while V != []:Select_V =random.choice(V)result = Select_i.Judge_whether_to_insert(Select_V)if result == True:  # 随机配置V.remove(Select_V)if V==[]:Selected_Sever.append(Select_i)breakif result == False:for i in range(len(V)):result = Select_i.Judge_whether_to_insert(V[i])if result == True:V.remove(V[i])breakif result == False and i >= len(V) - 1:Selected_Sever.append(Select_i)Select = random.choice(self.Sever)Select_i = Sever_Machine(Select)return Selected_Severreturn Selected_Severdef add_to_old(self,S,V):for i in range(len(S)):if V!=[]:random.shuffle(V)for V_i in V:result=S[i].Judge_whether_to_insert(V_i)if result==True:V.remove(V_i)return S,Vdef transfer(self,Sever,V_total):Transferable_num = int(len(V_total) * 5 / 1000)if Transferable_num>0:# for i in range(len())passelse:passreturn Severdef Virtual_use(self):Selected_Sever=[]V_total=[]for i in range(len(self.use_Case)):V_T = []for j in range(len(self.use_Case[i])):if self.use_Case[i][j][0] == 'add':for V_i in range(len(self.Virtual)):if self.use_Case[i][j][1] == self.Virtual[V_i][0]:V_I = Virtual_Machine(self.Virtual[V_i], self.use_Case[i][j][2])V_T.append(V_I)V_total.append(V_I)breakif self.use_Case[i][j][0] == 'del':for V_k in range(len(V_total)):if V_total[V_k].user == self.use_Case[i][j][1]:V_total.remove(V_total[V_k])for S_i in range(len(Selected_Sever)):if V_total[V_k].user in Selected_Sever[S_i].assigned:Selected_Sever[S_i].del_Virtual(V_total[V_k])breakbreakK = copy.copy(V_T)if Selected_Sever==[]:d = GA()Selected_Sever = d.main(K, self.Sever, len(self.use_Case) - i)Q=[]for i in range(len(Selected_Sever)):Q.append(Selected_Sever[i].Model)Q_set=set(Q)Q_num=len(list(Q_set))print('(Purchase,', Q_num, ')')for Q_i in Q_set:print('(',Q_i,',', Q.count(Q_i), ')')print('(migration,', 0, ')')New_order=[]for Si in Q_set:for Sv in Selected_Sever:if Sv.Model==Si:New_order.append(Sv)Selected_Sever=New_orderfor u_i in V_T:for S_v in range(len(Selected_Sever)):if u_i.user in Selected_Sever[S_v].assigned:if Selected_Sever[S_v].assigned_Node[Selected_Sever[S_v].assigned.index(u_i.user)]==1:print('(',S_v,',','A' , ')')if Selected_Sever[S_v].assigned_Node[Selected_Sever[S_v].assigned.index(u_i.user)]==2:print('(',S_v,',','B' , ')')if Selected_Sever[S_v].assigned_Node[Selected_Sever[S_v].assigned.index(u_i.user)]==0:print('(',S_v,  ')')else:Add=self.add_to_old(Selected_Sever,K)Old_Sever=Add[0]rest_V=Add[1]d = GA()Selected_Sever_1 = d.main(rest_V, self.Sever, len(self.use_Case) - i)Q = []for i in range(len(Selected_Sever_1)):Q.append(Selected_Sever_1[i].Model)Q_set = set(Q)Q_num = len(list(Q_set))print('(Purchase,', Q_num, ')')for Q_i in Q_set:print('(', Q_i, ',', Q.count(Q_i), ')')print('(migration,', 0, ')')New_order = []for Si in Q_set:for Sv in Selected_Sever_1:if Sv.Model == Si:New_order.append(Sv)Selected_Sever.extend(New_order)for u_i in V_T:for S_v in range(len(Selected_Sever)):if u_i.user in Selected_Sever[S_v].assigned:if Selected_Sever[S_v].assigned_Node[Selected_Sever[S_v].assigned.index(u_i.user)]==1:print('(',S_v,',','A' , ')')if Selected_Sever[S_v].assigned_Node[Selected_Sever[S_v].assigned.index(u_i.user)]==2:print('(',S_v,',','B' , ')')if Selected_Sever[S_v].assigned_Node[Selected_Sever[S_v].assigned.index(u_i.user)]==0:print('(',S_v,  ')')def Get_data(path):if os.path.exists(path):with open(path,'r') as data:Lis=data.readlines()Sever=[]Virtual=[]counter=0use_Case=[]while Lis:num=Lis[0].strip().split('\n')[0]if num.isdigit():Lis=Lis[1:len(Lis)]last_num=int(num)else:add_sentence=Lis[0:last_num]P=[]for i in range(len(add_sentence)):P_1=[]sentence = add_sentence[i]result=re.findall(r'[a-zA-Z0-9.]{1,}',sentence)for r_i in result:if r_i.isdigit():P_1.append(int(r_i))else:P_1.append(r_i)P.append(P_1)if counter==0:Sever=Pif counter==1:Virtual=Pif counter>1:use_Case.append(P)counter+=1Lis=Lis[last_num:len(Lis)]return Sever,use_Case,Virtualdef main():# to read standardA = Get_data('training-1.txt')# processd=daily_situation(A[0],A[2],A[1])d.Virtual_use()# to write standard output# sys.stdout.flush()if __name__ == "__main__":S=time.time()main()E=time.time()print(E)

输出：

 


http://chatgpt.dhexx.cn/article/m9P8K7Ed.shtml

相关文章

2020华为软挑总结

2020华为软挑总结

文章目录 一、热身赛编程闯关&#xff1a;评价标准&#xff1a;问题分析 二、初赛问题描述评价标准&#xff1a;问题分析思路一&#xff1a;思路二&#xff1a;思路三&#xff1a;针对思路三的提速&#xff1a; 最终结果&#xff1a; 三、code记录初赛两篇不错的总结三、复活赛…
阅读更多...
2022华为软挑比赛（初赛笔记）

2022华为软挑比赛（初赛笔记）

文章目录 2022华为软挑&#xff08;初赛笔记&#xff09;1. 赛题要求2. 解决方案2.1 挑选适合的边缘节点2.2 第一轮&#xff1a;最大分配2.3 第二轮&#xff1a;均值分配 总结 本文仓库地址&#xff1a; Github-CodeCraft-2022 2022华为软挑&#xff08;初赛笔记&#xff09; …
阅读更多...
2023华为软件精英挑战赛笔记心得（Python实现）

2023华为软件精英挑战赛笔记心得（Python实现）

第一次参加华为软挑&#xff0c;问了周围一圈人没人组队&#xff0c;看了眼题目&#xff0c;感觉挺有意思的&#xff0c;就打算自己写来跑一下&#xff0c;不求分数&#xff0c;主要是想学点东西&#xff0c;顺便记录一下。&#xff08;最后跑了195w&#xff0c;自己的能力也就…
阅读更多...
2021华为软件精英挑战总结

2021华为软件精英挑战总结

2021华为软挑32强总结 今年的软挑最终止步于粤港澳赛区第16名&#xff0c;总成本为16亿3979万6349&#xff0c;赛区第一名总成本为15亿3903万4817。 虽然没进入决赛&#xff0c;但是拿到了华为面试直通卡&#xff0c;也喜提广州一日游&#xff0c;算不虚此行了。决赛虽然还在继…
阅读更多...
Spring认证中国教育管理中心-Spring Data Neo4j教程一

Spring认证中国教育管理中心-Spring Data Neo4j教程一

原标题&#xff1a;Spring认证中国教育管理中心-Spring Data Neo4j教程一&#xff08;Spring中国教育管理中心&#xff09; 5. 开始 我们为 SDN 提供了 Spring Boot 启动器。请通过您的依赖管理包含启动模块并配置要使用的螺栓 URL&#xff0c;例如org.neo4j.driver.uribolt:/…
阅读更多...
SpringBoot 整合 Neo4j

SpringBoot 整合 Neo4j

1、创建测试类2、集成 SpringBoot 阅读此文之前&#xff0c;必须对 Neo4j 有个初步的了解&#xff0c;如果要实际操作的话&#xff0c;需要自备一个 Neo4j 数据库 本文所涉及代码已开源至 Gitee https://gitee.com/Array_Xiang/spring-boot-neo4j 创建一个 SpringBoot 项目&…
阅读更多...
【Neo4j教程之CQL函数基本使用】

【Neo4j教程之CQL函数基本使用】

&#x1f680; Neo4j &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;C…
阅读更多...
Neo4j资料 Neo4j教程 Neo4j视频教程 Neo4j 图数据库视频教程

Neo4j资料 Neo4j教程 Neo4j视频教程 Neo4j 图数据库视频教程

课程发布地址 地址&#xff1a; 腾讯课堂《Neo4j 图数据库视频教程》 https://ke.qq.com/course/327374?tuin442d3e14 作者 庞国明&#xff0c;《Neo4j权威指南》副主编、《Neo4j 3.x 入门经典》翻译 邮箱&#xff1a;pangguomingyeah.netQQ:1143815700Neo4j技术讨论QQ群&…
阅读更多...
Neo4J超详细专题教程，快来收藏起来吧

Neo4J超详细专题教程，快来收藏起来吧

Neo4J超详细教程 Lecture&#xff1a;波哥 一、Neo4J相关介绍 1.为什么需要图数据库 随着社交、电商、金融、零售、物联网等行业的快速发展&#xff0c;现实社会织起了了一张庞大而复杂的关系 网&#xff0c;传统数据库很难处理关系运算。大数据行业需要处理的数据之间的关系随…
阅读更多...
Neo4j教程 Neo4j视频教程 Neo4j 图数据库视频教程

Neo4j教程 Neo4j视频教程 Neo4j 图数据库视频教程

课程发布地址 地址&#xff1a; 腾讯课堂《Neo4j 图数据库视频教程》 https://ke.qq.com/course/327374?tuin442d3e14 作者 庞国明&#xff0c;《Neo4j权威指南》副主编、《Neo4j 3.x 入门经典》翻译 邮箱&#xff1a;pangguomingyeah.netQQ:1143815700Neo4j技术讨论QQ群&…
阅读更多...
neo4j教程-安装部署

neo4j教程-安装部署

neo4j教程-安装部署 Neo4j的关键概念和特点 •Neo4j是一个开源的NoSQL图形存储数据库&#xff0c;可为应用程序提供支持ACID的后端。Neo4j的开发始于2003年&#xff0c;自2007年转变为开源图形数据库模型。程序员使用的是路由器和关系的灵活网络结构&#xff0c;而不是静态表…
阅读更多...
Neo4j安装教程

Neo4j安装教程

1.下载社区版本&#xff0c;java8推荐安装3.*的版本 Neo4j Download Center - Neo4j Graph Data Platformhttps://neo4j.com/download-center/#community 点击下载即可。 2.配置 启动 将提取的文件放在服务器上的永久主页中&#xff0c;例如 D:\neo4j\. 顶级目录称为 NEO4J_…
阅读更多...
Neo4j详细介绍及使用教程

Neo4j详细介绍及使用教程

文章目录 一、Neo4j介绍1.Neo4j简介2.图数据库简介3.Neo4j的优缺点4.Neo4j的常见应用场景二、使用教程1.下载安装2.数据插入和查询(1)基本概念(2)基本语法Ⅰ.CREATE操作——创建Ⅱ.MERGE——创建或更新Ⅲ.Match操作——查找指定的图数据Ⅳ.DELETE操作——删除节点3.JAVA实战 一…
阅读更多...
Neo4j语法教程

Neo4j语法教程

neo4j简版教程 create (<node-name:<label-name2>:<label-name2>......>) return <node-name> 可以给一个节点创建多label的node eg: CREATE (dept:Dept { deptno:10,dname:"Accounting",location:"Hyderabad" }) Neo4j CQL创…
阅读更多...
【数据库】linux安装neo4j教程（neo4j 4.x）

【数据库】linux安装neo4j教程（neo4j 4.x）

一.配置jdk neo4j 4.x版本依赖jdk11&#xff0c;需要安装jdk11才能正常启动&#xff08;安装高版本或低版本jdk都不行&#xff09; 1&#xff09;执行uname -a看下系统架构 2&#xff09;根据系统架构下载对应安装包 https://www.oracle.com/java/technologies/javase/jdk11…
阅读更多...
linux neo4j 教程,Neo4j 入门教程 - 安装

linux neo4j 教程,Neo4j 入门教程 - 安装

本篇来简单介绍下如何下载并安装 Neo4j&#xff0c;篇目很短&#xff0c;因为真的很简单。 下载 Neo4j 首先在 https://neo4j.com/download/ 下载 Neo4j。你可以选择企业体验版或者免费的社区版&#xff0c;这里我是用的社区版。点击 Download 按钮即可开始下载。 网站会自动下…
阅读更多...
使用Docker安装neo4j教程

使用Docker安装neo4j教程

拉取镜像源 docker pull neo4j(:版本号) //缺省 “:版本号” 时默认安装latest版本的查看本地镜像 docker images启动容器 docker run -d --name container_name -p 7474:7474 -p 7687:7687 -v /home/neo4j/data:/data -v /home/neo4j/logs:/logs -v /home/neo4j/conf:/var…
阅读更多...
neo4j教程 java_neo4j 教程

neo4j教程 java_neo4j 教程

Neo4j是一个世界领先的开源图形数据库。 它是由Neo技术使用Java语言完全开发的。本教程将教你Neo4j的基础知识&#xff0c;Java与Neo4j和Spring DATA与Neo4j。 本教程分为Neo4j简介&#xff0c;Neo4j CQL&#xff0c;Neo4j CQL函数&#xff0c;Neo4j管理员&#xff0c;Neo4j与J…
阅读更多...
最详细的Neo4J解读（附安装教程）

最详细的Neo4J解读（附安装教程）

文章目录 一、Neo4j简介二、Neo4j - 特点和优势1.Neo4j的特点2.Neo4j的优点3.Neo4j的缺点或限制 三、Neo4j - 数据模型四、Neo4j安装及配置1.安装Java JDK2.下载安装Neo4j3.创建系统环境变量4.Neo4j的启动和停止5.切换数据库 五、Neo4j的CQL操作 一、Neo4j简介 Neo4j是一种流行…
阅读更多...
图数据库Neo4j实战（全网最详细教程）

图数据库Neo4j实战（全网最详细教程）

1.图数据库Neo4j介绍 1.1 什么是图数据库&#xff08;graph database&#xff09; 随着社交、电商、金融、零售、物联网等行业的快速发展&#xff0c;现实社会织起了了一张庞大而复杂的关系网&#xff0c;传统数据库很难处理关系运算。大数据行业需要处理的数据之间的关系随数…
阅读更多...
推荐文章

Copyright @ 2022~2023