【最新华为OD机试E卷】查找充电设备组合(200分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队｜大厂实习经历｜多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

🎀关于华为OD

✨华为OD的概念华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
⌚️华为 OD 应聘流程
- 第一步：投递简历
  - 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。
- 第二步：机试
  - 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。
- 第三步：技术面
  - 2 轮技术面试。
- 第四步：HR 与主管面试
- 第五步：录用，发 offer

alt

🍓OJ题目截图

alt

🔌 查找充电设备组合

问题描述

某个充电站可提供 $n$ 个充电设备，每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和，均构成功率集合 $P$ 的 1 个元素。功率集合 $P$ 的最优元素，表示最接近充电站最大输出功率 $p_{max}$ 的元素。

输入格式

输入为 3 行：

第 1 行为充电设备个数 $n$ 。
第 2 行为每个充电设备的输出功率。
第 3 行为充电站最大输出功率 $p_{max}$ 。

输出格式

输出功率集合 $P$ 的最优元素。

样例输入 1

4
50 20 20 60
90

样例输出 1

样例解释 1

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

样例输入 2

2
50 40
30

样例输出 2

样例解释 2

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

数据范围

充电设备个数 $n > 0$
最优元素必须小于或等于充电站最大输出功率 $p_{max}$

题解

这道题目本质上是一个变形的 0-1 背包问题。

我们需要从给定的充电设备中选择一些，使得它们的总功率最接近但不超过充电站的最大输出功率。

解题思路如下：

首先，我们可以使用动态规划来解决这个问题。创建一个数组 dp，其中 $dp[i]$ 表示是否可以达到功率 i。
初始化 $dp[0]$ = true，因为总是可以达到 $0$ 功率（不选择任何设备）。
遍历每个充电设备的功率，对于每个功率 power，更新 dp 数组：
- 如果 $dp[i]$ 为 true，那么 $dp[i + power]$ 也应该为 true。
最后，从 $p_max$ 开始向下遍历 dp 数组，找到第一个为 true 的索引，即为最优解。

时间复杂度分析：

设充电站最大输出功率为 M，充电设备数量为 N。
我们需要遍历每个充电设备（N次），对于每个设备，我们需要更新 dp 数组（最多 M 次）。
因此，总的时间复杂度为 O(N * M)。

参考代码

Python

def solve(n, powers, p_max):
    # 初始化dp数组，dp[i]表示是否可以达到功率i
    dp = [False] * (p_max + 1)
    dp[0] = True  # 总是可以达到0功率
    
    # 遍历每个充电设备的功率
    for power in powers:
        # 从大到小遍历，避免重复计算
        for i in range(p_max, power - 1, -1):
            if dp[i - power]:
                dp[i] = True
    
    # 从p_max开始向下查找第一个为True的索引
    for i in range(p_max, -1, -1):
        if dp[i]:
            return i
    
    return 0  # 如果没有找到合适的组合，返回0

# 读取输入
n = int(input())
powers = list(map(int, input().split()))
p_max = int(input())

# 计算并输出结果
result = solve(n, powers, p_max)
print(result)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int solve(int n, int* powers, int p_max) {
    // 动态分配内存给dp数组
    bool* dp = (bool*)calloc(p_max + 1, sizeof(bool));
    dp[0] = true;  // 总是可以达到0功率

    // 遍历每个充电设备的功率
    for (int j = 0; j < n; j++) {
        for (int i = p_max; i >= powers[j]; i--) {
            if (dp[i - powers[j]]) {
                dp[i] = true;
            }

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

最新华为OD机试-E+D卷文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测