【华为OD-E卷 - 查找充电设备组合 100分（python、java、c++、js、c）】
题目
某个充电站，可提供 n 个充电设备，每个充电设备均有对应的输出功率。
任意个充电设备组合的输出功率总和，均构成功率集合 P 的 1 个元素。
功率集合 P 的最优元素，表示最接近充电站最大输出功率 p_max 的元素
输入描述
- 输入为3行：
第1行为充电设备个数n 第2行为每个充电设备的输出功率 第3行为充电站最大输出功率p_max
输出描述
- 功率集合P的最优元素
备注
- 充电设备个数 n > 0 最优元素必须小于或等于充电站最大输出功率p_max
用例
用例一：
输入：
4
50 20 20 60
90
- 1
- 2
- 3
输出：
90
- 1
用例二：
输入：
2
50 40
30
- 1
- 2
- 3
输出：
0
- 1
python解法
- 解题思路：
- 问题描述
给定一个整数 n 表示可用的元素数量，每个元素具有一个“能力值”存储在数组 power_list 中。
目标是通过选择若干个元素的能力值，使其总和尽可能接近（不超过）给定的最大值 max_power。
输出最终能够达到的最大总和。
解决方案
动态规划 问题，类似于“背包问题”：
定义 dp[j] 表示容量为 j 时，能够达到的最大总和。
初始化 dp[0] = 0（容量为 0 时，总和为 0），其他值初始为 0。
遍历每个元素，对于当前元素的能力值 power，倒序更新 dp 数组：
如果选择当前能力值 power，更新 dp[j] = max(dp[j], dp[j - power] + power)。
这种倒序遍历保证了每个元素只被使用一次（即 0-1 背包的特性）。
如果在更新过程中，发现总和已经达到了 max_power，直接返回结果。
算法流程
初始化 dp 数组大小为 max_power + 1，初始值为 0。
遍历每个能力值 power，从后往前更新 dp 数组：
遍历范围为 [max_power, power]，更新 dp[j]。
如果在更新过程中，dp[j] == max_power，说明已经找到了最大可能值，直接输出结果并退出。
遍历所有能力值后，输出 dp[max_power]，即最终能够达到的最大总和
# 读取输入
n = int(input()) # 元素数量
power_list = list(map(int, input().split())) # 每个元素的能力值列表
max_power = int(input()) # 最大目标能力值
# 初始化动态规划数组，表示容量为 j 时能达到的最大总和
dp = [0] * (max_power + 1)
# 遍历每个能力值
for power in power_list:
# 倒序遍历，从 max_power 到 power
for j in range(max_power, power - 1, -1):
# 更新 dp 数组：选择当前能力值与不选择的最大值
dp[j] = max(dp[j], dp[j - power] + power)
# 如果达到了最大目标值，直接输出并退出
if dp[j] == max_power:
print(max_power)
exit()
# 遍历完成后输出结果，表示能达到的最大总和
print(dp[max_power])
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
java解法
- 解题思路
- 问题描述
有一个容量上限为 maxPower 的背包，以及 count 个物品，每个物品的“能力值”存储在数组 powerOutputs 中。
每个物品只能被选择一次，目标是找到一个组合，使得总能力值尽可能接近（但不超过）maxPower，并输出最大总和。
解决方案
这是一个典型的 0-1 背包问题：
使用动态规划解决，定义 dp[j] 表示在容量为 j 时能够达到的最大能力值。
遍历每个物品，对于每个物品的能力值 powerOutputs[i]，更新 dp 数组：
如果选择当前物品，更新 dp[j] = max(dp[j], dp[j - powerOutputs[i]] + powerOutputs[i])。
如果不选择当前物品，保持 dp[j] 不变。
使用倒序更新 dp 数组以确保每个物品只被使用一次。
算法流程
初始化一个大小为 maxPower + 1 的数组 dp，所有元素初始化为 0。
遍历每个物品的能力值 powerOutputs[i]：
从后向前遍历容量 j，范围是 [maxPower, powerOutputs[i]]。
更新 dp[j] 的值。
遍历所有物品后，dp[maxPower] 即为能够达到的最大总能力值
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// 读取物品数量
int count = input.nextInt();
// 读取每个物品的能力值
int[] powerOutputs = new int[count];
for (int i = 0; i < count; i++) {
powerOutputs[i] = input.nextInt();
}
// 读取背包的最大容量
int maxPower = input.nextInt();
// 调用动态规划方法计算最优能力值
System.out.println(findOptimalPower(count, powerOutputs, maxPower));
}
/**
* 使用动态规划求解背包问题，寻找最大能力值总和
*
* @param count 物品数量
* @param powerOutputs 每个物品的能力值
* @param maxPower 背包的最大容量
* @return 能够达到的最大能力值总和
*/
public static int findOptimalPower(int count, int[] powerOutputs, int maxPower) {
// 动态规划数组，表示容量为 j 时的最大能力值
int[] dp = new int[maxPower + 1];
// 遍历每个物品
for (int i = 0; i < count; i++) {
// 从后向前更新 dp 数组，确保每个物品只使用一次
for (int j = maxPower; j >= powerOutputs[i]; j--) {
// 更新 dp[j]，选择或不选择当前物品
dp[j] = Math.max(dp[j], dp[j - powerOutputs[i]] + powerOutputs[i]);
}
}
// 返回能够达到的最大能力值
return dp[maxPower];
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
给定一个数组 powers 表示若干个物品的能力值，以及一个整数 maxPower 表示背包的容量上限。
目标是从 powers 中选择若干物品，使得其能力值总和尽可能接近（但不超过）maxPower，并输出最大总和。
解决方案
使用递归 + 记忆化（动态规划）解决问题。
定义递归函数 findMax(index, remainingPower)：
index 表示当前正在考虑的物品索引。
remainingPower 表示背包剩余的容量。
返回在当前状态下能够达到的最大能力值总和。
记忆化数组 memo 用于存储中间结果，避免重复计算：
memo[index][remainingPower] 表示从物品 index 开始、背包剩余容量为 remainingPower 时能够达到的最大能力值。
递归逻辑
终止条件：
如果当前物品索引 index 已超出数组范围，返回 0（表示没有更多物品可选）。
状态转移：
不选择当前物品：结果为 findMax(index + 1, remainingPower)。
选择当前物品（如果其能力值不超过剩余容量）：结果为 powers[index] + findMax(index + 1, remainingPower - powers[index])。
最终结果为上述两种选择的最大值。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
// 读取输入数据
rl.on("line", (line) => {
lines.push(line);
// 当读取到 3 行数据时，开始处理
if (lines.length === 3) {
const n = parseInt(lines[0]); // 物品数量
const powers = lines[1].split(" ").map(Number); // 物品能力值数组
const maxPower = parseInt(lines[2]); // 背包容量
// 调用主函数，计算结果
console.log(getOptimalPower(n, powers, maxPower));
// 重置输入缓冲区
lines.length = 0;
}
});
/**
* 主函数：计算背包问题的最优解
* @param {number} n 物品数量
* @param {number[]} powers 物品能力值数组
* @param {number} maxPower 背包的最大容量
* @returns {number} 能够达到的最大能力值
*/
function getOptimalPower(n, powers, maxPower) {
// 初始化记忆化数组，默认值为 -1，表示尚未计算
const memo = Array(n)
.fill(null)
.map(() => Array(maxPower + 1).fill(-1));
// 调用递归函数，返回最终结果
return findMax(0, maxPower, powers, memo);
}
/**
* 递归函数：计算从当前物品开始、剩余容量为 remainingPower 时的最大能力值
* @param {number} index 当前物品索引
* @param {number} remainingPower 背包剩余容量
* @param {number[]} powers 物品能力值数组
* @param {number[][]} memo 记忆化数组
* @returns {number} 当前状态下能够达到的最大能力值
*/
function findMax(index, remainingPower, powers, memo) {
// 递归终止条件：如果已经处理完所有物品，返回 0
if (index === powers.length) return 0;
// 如果当前状态已经计算过，直接返回缓存值
if (memo[index][remainingPower] !== -1) return memo[index][remainingPower];
// 不选择当前物品
let withoutCurrent = findMax(index + 1, remainingPower, powers, memo);
// 选择当前物品（如果能力值不超过剩余容量）
let withCurrent = 0;
if (powers[index] <= remainingPower) {
withCurrent =
powers[index] +
findMax(index + 1, remainingPower - powers[index], powers, memo);
}
// 记录当前状态的最优解，并返回
memo[index][remainingPower] = Math.max(withoutCurrent, withCurrent);
return memo[index][remainingPower];
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：