首页 > 试题广场 >

有限资源下的任务部署

[编程题]有限资源下的任务部署

热度指数：74 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

途虎养车公司机房中的一台某台服务器的上使用虚拟化技术可以承载多个不同的计算任务，但是因为服务器算力的约束，一台机器能承载的服务量始终是有限的。已知一台服务器的算力为m，有w个不同的任务需要部署，每个任务占用的算力与产生的价值分别为p[i],v[i],请问在这台服务器上部署任务能产生的最大价值是多少？

输入描述:


输入第一行有两个整数m,w。(0 <=m <= 1000,0 <= w <= 1000) 代表机器的总算力和任务数
然后有w行数据，每行有两个整数，p[i],v[i] 代表第i个任务的算力和价值。0 <= p[i] <= 100000,0 <= v[i] <= 100000

输出描述:

输出一个整数，代表在这台服务上部署任务能产生的最大价值

示例1

输入

输出

算法知识视频讲解

pein531

一个典型的动规背包问题：一个背包容量有限，怎么装包能使包中的物品价值最大

m, w = map(int, input().strip().split())
p, v = [], []
for _ in range(w):
    temp = list(map(int, input().strip().split()))
    p.append(temp[0])
    v.append(temp[1])
# 求解背包问题
dp = [0]*(m + 1)    # dp[i]表示消耗i所产生的最大价值，显然dp[0]=0
for i in range(1, w + 1):
    for j in range(m, p[i - 1] - 1, -1):
        dp[j] = max(dp[j - p[i - 1]] + v[i - 1], dp[j])
print(dp[m])

发表于 2021-01-20 13:42:52 回复(0)

Python

maoxiaomao

m,w=map(int, input().strip().split())
A=[]
A.append([0,0])
for i in range(w):
    A.append(list(map(int, input().strip().split()))) 
dp=[[0]*(m+1) for _ in range(w+1)]
for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if j<A[i][0]:      #装不下
            dp[i][j]=dp[i-1][j]
        else:              #最大价值=max(上一个单元格最大价值，当前价值+剩余算力的最大价值) 
            dp[i][j]=max(dp[i-1][j],A[i][1]+dp[i-1][j-A[i][0]])  
print(dp[-1][-1])

发表于 2021-06-04 14:45:59 回复(0)