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

声明

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

题目描述

考虑到在虚拟机部署中资源提供商通常希望自己的收益最大化，现假设有一台宿主机，共有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和内存容量不能满足任何一个用户要求为止，最优解便求得。

测试结果

运行结果:

源代码

import sys
print("请输入申请虚拟机的用户个数，cpu个数，内存容量：")
a = list(map(int, input().split()))  # 用数组a来存储参与报价的用户的个数,云端要存储的cpu个数，容量大小
a1 = a[0]  # 存储用户个数，要输入几行数据
a2 = a[1]  # 存储cpu的个数
a3 = a[2]  # 存储容量
b = []
cpu_num=0
size_num=0
money=0

b1 = [0]*a1  #数组b1存储用户报价
p1 = [0]*a1  #数组p1记录报价金额的位置

for i in range(a1):
    print("请输入第",i+1,"个用户的申请CPU个数 内存容量 报价：")
    b.append(list(map(int, input().split())))

for k in range(a1):
	b1[k] = b[k][2]
	p1[k] = k  

for i in range(0,a1-1):
    for j in range(1,a1-i):
        if b1[j]>b1[j-1]:
            temp=b1[j-1]
            b1[j-1]=b1[j]
            b1[j]=temp
            temp=p1[j-1]
            p1[j-1]=p1[j]
            p1[j]=temp
def Fun(i):
    global cpu_num,size_num,money
    cpu_num=cpu_num+b[p1[i]][0]
    size_num=size_num+b[p1[i]][1]
    money=money+b[p1[i]][2]

    if cpu_num>a2 or size_num>a3:
        money=money-b[p1[i]][2]
        cpu_num=cpu_num-b[p1[i]][0]
        size_num=size_num-b[p1[i]][1]

for i in range(a1):
    Fun(i)
print("最大化收益：",money)

到此这篇关于Python动态规划实现虚拟机部署的文章就介绍到这了,更多相关Python虚拟机部署内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 动态规划之矩阵连乘问题Python实现方法

    动态规划之矩阵连乘问题Python实现方法

    本文实例讲述了动态规划之矩阵连乘问题Python实现方法.分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,-,An},其中Ai与Ai+1是可乘的,i=1,2 ,-,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少. 例如: A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 结果为:((A1(A2A3))((A4A5)A6))  最小的乘次为15125.

  • Python基于动态规划算法计算单词距离

    本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("

  • Python基于动态规划算法解决01背包问题实例

    Python基于动态规划算法解决01背包问题实例

    本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re

  • Python脚本判断 Linux 是否运行在虚拟机上

    在 WebHostingTalk 论坛上有些国外奸商会把虚拟机当作独立服务器卖,去年7月份的时候就有一位中国同胞上当受骗,并在 WHT 上发帖声讨,证据确凿,甚至连服务商自己也承认,回帖达355篇.这家独立服务器/VPS 提供商 HostATree.com 居然大胆的把 OpenVZ VPS 这种一看就知道是虚拟机的虚拟机当作独立服务器卖,晕,至少也要弄个 VMWare/KVM/Xen HVM 吧(更难发现是虚拟机),用 OpenVZ 这种容器也太欺负人了:)昨天恰好收到网友一封邮件问到了如何判

  • Windows下Pycharm远程连接虚拟机中Centos下的Python环境(图文教程详解)

    由于最近学习tensorflow的需要,tensorflow是在Linux环境下,使用的是Python.为了方便程序的调试,尝试在Windows下的Pycharm远程连接到虚拟机中Centos下的Python环境.(这里我采用的是ssh的远程连接) 1.准备工作: 固定centos的IP,这里我的固定IP为 192.168.254.128 . centos中安装ssh.(这里我采用的是ssh的远程连接) centos中Python环境已安装. 2.打开Pycharm,File->Settings

  • python实现对求解最长回文子串的动态规划算法

    基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

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

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

    声明 本文章为个人拙见,仅仅提供参考,不一定正确,各位大佬可以发表自己的意见. 题目描述 考虑到在虚拟机部署中资源提供商通常希望自己的收益最大化,现假设有一台宿主机,共有x个cpu和y GB的内存,用户可以采取自己报价的方式向资源提供商申请使用虚拟机资源,譬如说付w元申请a个cpu和b GB内存的一台虚拟机.请你设计一个算法,让资源提供商可以合理地安排虚拟机,使得自己的收益最大化. 输入: n x y 2 4 200 4 2 150 - 说明,n表示共有n条用户报价申请,宿主机共有x个cpu和y

  • Python算法思想集结深入理解动态规划

    目录 1. 概述 什么是重叠子问题 动态规划与分治算法的区别 什么最优子结构 2. 流程 2.1 是否存在子问题 2.2 是否存在重叠子问题 怎么解决重叠子问题 2.3 状态转移 3.总结 1. 概述 动态规划算法应用非常之广泛. 对于算法学习者而言,不跨过动态规划这道门,不算真正了解算法. 初接触动态规划者,理解其思想精髓会存在一定的难度,本文将通过一个案例,抽丝剥茧般和大家聊聊动态规划. 动态规划算法有 3 个重要的概念: 重叠子问题. 最优子结构. 状态转移. 只有吃透这 3 个概念,才叫

  • python动态规划算法实例详解

    如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划 斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项 代码如下: #

  • Java使用动态规划算法思想解决背包问题

    Java使用动态规划算法思想解决背包问题

    目录 动态规划算法 动态规划算法的思想 最优性原理 动态规划算法的三大特点 动态规划算法中的0/1背包问题 动态规划算法的优点 小结 动态规划算法 动态规划算法的思想 动态规划算法处理的对象是多阶段复杂决策问题,动态规划算法和分治算法类似,其基本思想也是将待求解问题分解成若干个子问题(阶段),然后分别求解各个子问题(阶段),最后将子问题的解组合起来得到原问题的解,但是与分治算法不同的是,子问题往往不是相互独立的,而是相互联系又相互区别的 动态规划算法问题求解的目标是获取导致问题最优解的最优决策序

  • python最长回文串算法

    给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串.所谓回文性是指诸如 "aba","ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质. 看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度.显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N).所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两

  • 使用Python的开发框架Brownie部署以太坊智能合约

    使用Python的开发框架Brownie部署以太坊智能合约

    介绍 我希望可以在任何开发场景都尽量用Python.在区块链开发中,常用的是以太坊虚拟机智能合约语言Solidity,它具有许多不错的功能,并且仍然可以使用 Python 进行部署.刚开始使用Solidity时,我使用了Remix(https://remix.ethereum.org/),这是一个强大的Web IDE,可让您进行智能合约可视化.Remix很棒,我现在仍然使用它,但是在单个IDE之外可以实现很多其他功能.后来我开始学习Truffle(https://www.trufflesuite

  • Python机器学习之手写KNN算法预测城市空气质量

    Python机器学习之手写KNN算法预测城市空气质量

    目录 一.KNN算法简介 二.KNN算法实现思路 三.KNN算法预测城市空气质量 1. 获取数据 2. 生成测试集和训练集 3. 实现KNN算法 一.KNN算法简介 KNN(K-Nearest Neighbor)最邻近分类算法是数据挖掘分类(classification)技术中常用算法之一,其指导思想是"近朱者赤,近墨者黑",即由你的邻居来推断出你的类别. KNN最邻近分类算法的实现原理:为了判断未知样本的类别,以所有已知类别的样本作为参照,计算未知样本与所有已知样本的距离,从中选取与

  • python数据结构leetcode338比特位计数算法

    目录 一.题目内容 示例 1: 示例 2: 进阶: 二.解题思路 三.代码 一.题目内容 给定一个非负整数 num.对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回. 示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2] 进阶: 给出时间复杂度为O(n*sizeof(integer))的解答非常容易.但你可以在线性时间O(n)内用一趟扫描做到吗? 要求算法的空间复杂度为O(n). 你能进

  • Python实现破解猜数游戏算法示例

    本文实例讲述了Python实现破解猜数游戏算法.分享给大家供大家参考,具体如下: QQ群里的聊天机器人会发起猜数小游戏. 玩法如下: 1. 用户发 #猜数    到群里 2. 机器人响应: 猜数已经开始, 范围是1-10000之间的某个数 3. 你发送 #猜数[123] 到群里 4. 机器人响应: 大了或者小了, 或者恭喜你猜中了 5. 你根据刚才猜的123, 和返回, 猜一个更小或更大的数, 发送 #猜数[111] , 即返回第2步 那么最好的猜测方法肯定是找居中的数了, 由于心算耗时, 所以

  • XenServer 安装及虚拟机部署详细指南

    1 了解服务器配置 1.1 查看服务器CPU是否支持虚拟化 1.1.1 目的 目前Inter和AMD生产的主流CPU都支持虚拟化技术,但很多电脑或主板BIOS出厂时默认禁用虚拟化技术 1.1.2 方法 setp1: 重启服务器后按F2或F10进入BIOS界面(不同主板型号进入BIOS所需按键不同) setp2:将BIOS显示切换到Process的面板,由于主板不一样其BIOS中显示关键词也不一样,主要是找到Virtual或Virtualization将其设置为Enabled setp3:退出BI

随机推荐