题目描述:
某个充电站,可提供n个充电设备,每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和,均构成功率集合P的1个元素。功率集合P的最优元素,表示最接近充电站最大输出功率p_max的元素。
输入描述:
输入为3行:
第1行为充电设备个数n。
第2行为每个充电设备的输出功率。
第3行为充电站最大输出功率p_max。
输出描述:
功率集合P的最优元素
补充说明:
1.充电设备个数n>0
2.最优元素必须小于或等于充电站最大输出功率p_max。
import sys
n = sys.stdin.readline().strip()
n = int(n)
line = sys.stdin.readline().strip()
p = list(map(int, line.split()))
limit = sys.stdin.readline().strip()
limit = int(limit)
dp = [[0] * (limit + 2) for _ in range(n+1)]
p.sort()
for i in range(1, n+1):
for j in range(0, limit+2):
if j < p[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j-p[i-1]] + p[i-1], dp[i-1][j])
# print(len(dp), len(dp[0]))
ans