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)

파 이 썬 의 동적 계획 이 가상 컴퓨터 배 치 를 실현 하 는 것 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 파 이 썬 가상 컴퓨터 배치 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 십시오.앞으로 많은 지원 을 바 랍 니 다!