已知存在n个宝物,每个宝物都有自己的质量m和价值v,在考虑选择宝物时只能选择总质量小于等于M的方案,请问在最优方案下选择宝物,能获取到最大价值V是多少?
(第一行输入宝物的数量n(1
v代表每个宝物自己的价值
m代表每个宝物的质量
V代表最大价值
M代表总质量)
class Solution:
def __init__(self) -> None:
pass
def solution(self, n, M, vector):
if n <= 1 or n >= 100 or M < 1 or M > 1000:
return "错误"
else:
result = 0
t = 0
for i in range(len(vector)-1):
if vector[i][1] <= 1 or vector[i][1] >= 100 or vector[i][0] <= 1 or vector[i][0] >= 100:
return "错误"
else:
for j in range(len(vector) -i-1):
if vector[j][1] / vector[j][0] == vector[j+1][1] / vector[j+1][0]:
if vector[j][0]1][1]:
p = vector[j]
vector[j] = vector[j + 1]
vector[j + 1] = p
elif vector[j][1] / vector[j][0] < vector[j+1][1] / vector[j+1][0]:
p = vector[j]
vector[j] = vector[j+1]
vector[j+1] = p
for p in vector:
t = p[0] + t
result = p[1] + result
if t > M:
t = t - p[0]
result = result - p[1]
return result
if name == "main":
arr_temp = [int(item) for item in input().strip().split()]
n = int(arr_temp[0])
M = int(arr_temp[1])
vector = []
for i in range(n):
vector.append([int(item) for item in input().strip().split()])
sol = Solution()
result = sol.solution(n, M, vector)
print(result)