华为OD机试-查找充电设备组合-2022Q4 A卷-Py/Java/JS

某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和，均构成功率集合P的1个元素。功率集合P的最优元素，表示最接近充电站最大输出功率P_max的元素
输入描述
输入为3行:
第1行为充电设备个数n
第2行为每个充电设备的输出功率P_i
第3行为充电站最大输出功率P_max

输出描述
功率集合P的最优元素
备注
充电设备个数 n >0
最优元素必须小于或等于充电站最大输出功率P_max
示例1：

输入

4
50 20 20 60

90
输出

90
说明
当充电设备输出功率50、20、20组合时，其输出功率总和为90，最接近充电站最大充电输出功率，因此最优元素为90。

示例2：

2
50 40

30
输出
0
说明
所有充电设备的输出功率组合，均大于充电站最大充电输出功率30，此时最优元素值为0。

Java 代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;
import java.math.BigInteger;
import java.util.stream.Stream;class Main {public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);int n = in.nextInt();in.nextLine();Integer[] p = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);int p_max = in.nextInt();//dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。int[][] dp = new int[n + 1][p_max + 1];// 初始化, i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。for (int j = p_max; j >= p[0]; j--) {dp[0][j] = dp[0][j - p[0]] + p[0];}for (int i = 1; i < n; i++) {  // 遍历物品for (int j = 0; j <= p_max; j++) { // 遍历背包容量// 背包容量为j，如果物品i的体积，此时dp[i][j]就是dp[i - 1][j]if (j < p[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p[i]] + p[i]);}}}System.out.println(dp[n-1][p_max]);}}

Python代码

import functools
import sys
from collections import Counter, defaultdict
import copy
from itertools import permutations
import re
import math
import sys#处理输入
n = int(input())
p = [int(x) for x in input().split(" ")]
p_max = int(input())#dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
dp = [[0 for x in range(p_max + 1)] for y in range(n+1)]# 初始化, i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
j = p_max
while(j >= p[0]):dp[0][j] = dp[0][j - p[0]] + p[0]j -= 1for i in range(1, n):  # 遍历物品for j in range(0, p_max+1): # 遍历背包容量# 背包容量为j，如果物品i的体积，此时dp[i][j]就是dp[i - 1][j]if (j < p[i]):dp[i][j] = dp[i - 1][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i]] + p[i])print(dp[n-1][p_max])

JS代码

function main(n,p,p_max) {//dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。let dp = new Array(n+1)for (let i=0;i<n+1;i++) {dp[i] = new Array(p_max+1).fill(0)}// 初始化, i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。let j = p_maxwhile(j >= p[0]){dp[0][j] = dp[0][j - p[0]] + p[0]j -= 1}for (let i=1;i<n;i++){  // 遍历物品for (let j=0;j<p_max+1;j++) { // 遍历背包容量// 背包容量为j，如果物品i的体积，此时dp[i][j]就是dp[i - 1][j]if (j < p[i])dp[i][j] = dp[i - 1][j]elsedp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p[i]] + p[i])}}console.log(dp[n-1][p_max])}main(4,[50, 20, 20, 60],90)