快捷導(dǎo)航

Python動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)虛擬機(jī)部署的算法思想

更新時(shí)間：2021年07月22日 11:14:58 作者：常子Aka

這篇文章主要介紹了Python動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)虛擬機(jī)部署的算法思想，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

聲明

本文章為個(gè)人拙見(jiàn)，僅僅提供參考，不一定正確，各位大佬可以發(fā)表自己的意見(jiàn)。

題目描述

考慮到在虛擬機(jī)部署中資源提供商通常希望自己的收益最大化，現(xiàn)假設(shè)有一臺(tái)宿主機(jī)，共有x個(gè)cpu和y GB的內(nèi)存，用戶可以采取自己報(bào)價(jià)的方式向資源提供商申請(qǐng)使用虛擬機(jī)資源，譬如說(shuō)付w元申請(qǐng)a個(gè)cpu和b GB內(nèi)存的一臺(tái)虛擬機(jī)。請(qǐng)你設(shè)計(jì)一個(gè)算法，讓資源提供商可以合理地安排虛擬機(jī)，使得自己的收益最大化。
輸入：
n x y
2 4 200
4 2 150
…
說(shuō)明，n表示共有n條用戶報(bào)價(jià)申請(qǐng)，宿主機(jī)共有x個(gè)cpu和y GB的內(nèi)存；
以下n行，每行表示用戶申請(qǐng)的cpu和內(nèi)存數(shù)，以及用戶報(bào)價(jià)的金額。

算法思想

該問(wèn)題為尋找全局最優(yōu)解問(wèn)題，采用動(dòng)態(tài)規(guī)劃的思想。找最大利益是最終的問(wèn)題，可以將最大利益的子問(wèn)題看做是已經(jīng)報(bào)價(jià)的每個(gè)用戶最大金額，并將其所要求的CPU數(shù)和內(nèi)存數(shù)加入到總的需求總，與提供的CPU數(shù)和內(nèi)存容納進(jìn)行對(duì)比。解決了目前最大報(bào)價(jià)的用戶，下一個(gè)最大報(bào)價(jià)又可以看做是一個(gè)子問(wèn)題，但CPU和內(nèi)存容量需要減去已經(jīng)分配的，如此反復(fù)，到CPU和內(nèi)存容量不能滿足任何一個(gè)用戶要求為止，最優(yōu)解便求得。

測(cè)試結(jié)果

運(yùn)行結(jié)果:

在這里插入圖片描述

源代碼

import sys  
print("請(qǐng)輸入申請(qǐng)?zhí)摂M機(jī)的用戶個(gè)數(shù)，cpu個(gè)數(shù)，內(nèi)存容量：")
a = list(map(int, input().split()))  # 用數(shù)組a來(lái)存儲(chǔ)參與報(bào)價(jià)的用戶的個(gè)數(shù),云端要存儲(chǔ)的cpu個(gè)數(shù)，容量大小  
a1 = a[0]  # 存儲(chǔ)用戶個(gè)數(shù)，要輸入幾行數(shù)據(jù)  
a2 = a[1]  # 存儲(chǔ)cpu的個(gè)數(shù)  
a3 = a[2]  # 存儲(chǔ)容量  
b = []
cpu_num=0
size_num=0
money=0

b1 = [0]*a1  #數(shù)組b1存儲(chǔ)用戶報(bào)價(jià)   
p1 = [0]*a1  #數(shù)組p1記錄報(bào)價(jià)金額的位置

for i in range(a1):
    print("請(qǐng)輸入第",i+1,"個(gè)用戶的申請(qǐng)CPU個(gè)數(shù) 內(nèi)存容量 報(bào)價(jià)：")
    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)

到此這篇關(guān)于Python動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)虛擬機(jī)部署的文章就介紹到這了,更多相關(guān)Python虛擬機(jī)部署內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: