编程题

Python

动态规划
2018-05-02

n座金矿，每座价值v，每座需要w人开发，现有m人，求开发金矿最大收益金矿。
输入：
5 10
3 4 3 5 5
200 300 350 400 500
输出：
900

[n,m]=[int(i) for i in input().split()]#n是金矿数量,m是工人数量
w=list(map(int,input().split()))#w是对应的金矿所需要的人数
v=list(map(int,input().split()))#v是对应的金矿的价值
dic={}
for i in range(m+1):
    dic[(i,0)]=v[0] if i>=w[0] else 0
for j in range(1,n):
    for i in range(m+1):
        dic[(i,j)]=max(dic[(i-w[j],j-1)]+v[j],dic[(i,j-1)]) if i>=w[j] else dic[(i,j-1)]
print(dic)