Python动态规划实现虚拟机部署的算法思想

avatar 2021年12月12日10:25:11 评论 73

声明

本文章为个人拙见,仅仅提供参考,不一定正确,各位大佬可以发表自己的意见。

题目描述

考虑到在虚拟机部署中资源提供商通常希望自己的收益最大化,现假设有一台宿主机,共有x个cpu和y GB的内存,用户可以采取自己报价的方式向资源提供商申请使用虚拟机资源,譬如说付w元申请a个cpu和b GB内存的一台虚拟机。请你设计一个算法,让资源提供商可以合理地安排虚拟机,使得自己的收益最大化。
输入:
n x y
2 4 200
4 2 150

说明,n表示共有n条用户报价申请,宿主机共有x个cpu和y GB的内存;
以下n行,每行表示用户申请的cpu和内存数,以及用户报价的金额。

算法思想

该问题为寻找全局最优解问题,采用动态规划的思想。找最大利益是最终的问题,可以将最大利益的子问题看做是已经报价的每个用户最大金额,并将其所要求的CPU数和内存数加入到总的需求总,与提供的CPU数和内存容纳进行对比。解决了目前最大报价的用户,下一个最大报价又可以看做是一个子问题,但CPU和内存容量需要减去已经分配的,如此反复,到CPU和内存容量不能满足任何一个用户要求为止,最优解便求得。

测试结果

运行结果:

在这里插入图片描述

源代码

文章来源于互联网:Python动态规划实现虚拟机部署的算法思想

历史上的今天
12月
12
avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: