当前位置：首页 > news >正文

华为OD机试 - 核酸最快检测效率 - 动态规划、背包问题（Python/JS/C/C++ 2024 E卷 200分）

news 2025/5/9 9:16:45

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

在系统、网络均正常的情况下组织核酸采样员和志愿者对人群进行核酸检测筛查。

每名采样员的效率不同，采样效率为 N 人/小时。

由于外界变化，采样员的效率会以 M 从小时为单位发生变化，M 为采样效率浮动粒度，M = N10%，输入保证 N10% 的结果为整数。

采样员效率浮动规则：采样员需要一名志愿者协助才能发挥正常效率，在此基础上，每增加一名志愿者，效率提升 1M，最多提升 3M；如果没有志愿者协助则组员，效率下降 2M。

怎么安排速度最快？求总最快检测效率（检测效率为各采样员效率值相加）。

二、输入描述

第一行：第一个值，采样员人数，取值范围 [1,100]；第二个值，志愿者人数，取值范围 [1,500]；
第二行：各采样员基准效率值（单位人/小时），保证输入中的每个项值计算 10% 为整数。

三、输出描述

第一行：总最快检测效率（单位人/小时）

四、测试用例

测试用例1：

1、输入

2 2
200 200

2、输出

400

3、说明

输入需要保证采样员基准效率值序列的每个值*10% 为整数。

五、解题思路

1、动态规划

动态规划是一种将问题分解为子问题，通过解决子问题来解决原问题的算法思想。其核心思想是：通过记忆化存储已经解决的子问题的结果，避免重复计算，从而提高算法的效率。

动态规划通常适用于满足以下条件的问题：

最优子结构：问题的最优解包含其子问题的最优解。
重叠子问题：同一个子问题会被多次计算，可以通过记忆化来减少重复计算。

动态规划常见于求解优化问题，比如求解最短路径、最大值等。

动态规划的步骤：

状态定义：确定如何用状态表示一个子问题的解。
状态转移方程：根据问题描述，推导如何从已知的状态转移到其他状态。
初始状态：设定一些基本情况，即子问题的最简单形式。
结果获取：通过状态转移方程迭代，最后在某个状态中得到问题的最终解。

2、背包问题

背包问题是一类经典的优化问题。背包问题的基本形式是：给定一个固定容量的背包和若干物品，每个物品有一定的重量和价值。需要选择哪些物品放入背包中，使得背包中的物品总重量不超过背包容量的前提下，物品的总价值最大化。

背包问题的分类：

0-1背包问题：每个物品只能选一次。
完全背包问题：每个物品可以选无数次。
多重选择背包问题（Multiple-Choice Knapsack Problem, MCKP）：每个物品可以有多个选择，不同的选择对应不同的重量和价值。
多重背包问题：每个物品有一定数量的限制。

3、为什么本题是背包问题

本题的目标是在给定志愿者数量的约束下，为多个采样员分配志愿者，使得总检测效率最大化。这个问题可以视为一种背包问题：

背包容量：总志愿者人数，类似于背包问题中的背包容量。
物品：每个采样员对应一个物品。
每个采样员有多个选择（类似于MCKP中的多重选择）：
- 选择0名志愿者：效率降低。
- 选择1至4名志愿者：效率逐渐增加。

因此，本题的结构和背包问题非常相似：我们有一个“容量”（志愿者总数）的限制，要求在该容量内进行多项选择，从而使得“价值”（总检测效率）最大。

4、为什么采用动态规划解决

（1）最优子结构

问题的最优解可以通过多个采样员的最优志愿者分配组合来获得。每个采样员如何分配志愿者，都会影响其检测效率；总的检测效率是所有采样员效率的和。因此问题的最优解包含了各个子问题的最优解（即每个采样员的最优志愿者分配方案）。

（2）重叠子问题

由于多个采样员共享相同的志愿者数量约束，不同采样员的分配可能会使用相同的志愿者数量，因此可以通过记忆化保存已计算的中间结果，避免重复计算，优化求解效率。

（3）多重选择

每个采样员有多个志愿者分配方案（0名志愿者、1名志愿者、2名志愿者等），对应不同的效率值。通过动态规划的状态转移，可以从一个状态逐步计算到更高的状态，找到最优的分配方案。

5、本题的动态规划应用如下：

状态定义：设 dp[v] 表示分配了 v 名志愿者时的最大检测效率。
状态转移：对于每个采样员，考虑给该采样员分配不同数量的志愿者（0到4名），计算每种情况下的效率，并更新DP数组：
- 若当前已经分配了 j 名志愿者，则可以选择为当前采样员再分配 cost 名志愿者（cost 为0至4），并根据此时的效率更新状态。
初始状态：当未分配任何志愿者时（即 dp[0]），检测效率为0。
结果获取：通过DP数组的最后一个状态，找到在不超过总志愿者数的情况下，最大的检测效率。

六、Python算法源码

# Python版本# 导入sys模块用于读取输入
import sysdef main():# 读取所有输入并按空白字符分割input = sys.stdin.read().split()idx = 0  # 初始化索引S = int(input[idx])  # 采样员人数idx += 1V = int(input[idx])  # 志愿者人数idx += 1N = []  # 初始化采样员基准效率列表for _ in range(S):N.append(int(input[idx]))  # 读取每个采样员的基准效率idx += 1# 初始化DP数组，长度为V+1，初始值为-无穷dp = [-float('inf')] * (V + 1)dp[0] = 0  # 无志愿者时，效率为0# 遍历每个采样员for i in range(S):M = N[i] // 10  # 计算M_idp_next = [-float('inf')] * (V + 1)  # 创建新的DP数组for j in range(V + 1):if dp[j] == -float('inf'):continue  # 如果当前状态不可达，跳过# 遍历当前采样员的所有分配选项（0到4名志愿者）for volunteers in range(0, 4 + 1):cost = volunteers  # 当前分配方案需要的志愿者数量if j + cost > V:continue  # 超过总志愿者数，跳过if volunteers == 0:efficiency = N[i] - 2 * M  # 无志愿者时效率下降else:extra = volunteers - 1  # 额外志愿者数量if extra > 3:extra = 3  # 最多提升3Mefficiency = N[i] + extra * M  # 计算效率# 更新dp_next数组if dp[j] + efficiency > dp_next[j + cost]:dp_next[j + cost] = dp[j] + efficiencydp = dp_next  # 更新DP数组# 寻找最大总效率max_efficiency = max(dp)print(max_efficiency)  # 输出结果# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

// JavaScript版本// 使用readline模块读取输入
const readline = require('readline');// 创建接口实例
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = []; // 存储所有输入// 读取每一行输入
rl.on('line', function(line){input = input.concat(line.trim().split(/\s+/)); // 按空白字符分割并加入输入数组
}).on('close', function(){let idx = 0; // 初始化索引const S = parseInt(input[idx++]); // 采样员人数const V = parseInt(input[idx++]); // 志愿者人数const N = []; // 初始化采样员基准效率数组for(let i = 0; i < S; i++){N.push(parseInt(input[idx++])); // 读取每个采样员的基准效率}// 初始化DP数组，长度为V+1，初始值为-Infinitylet dp = Array(V + 1).fill(-Infinity);dp[0] = 0; // 无志愿者时，效率为0// 遍历每个采样员for(let i = 0; i < S; i++){const M = Math.floor(N[i] / 10); // 计算M_ilet dp_next = Array(V + 1).fill(-Infinity); // 创建新的DP数组for(let j = 0; j <= V; j++){if(dp[j] === -Infinity){continue; // 如果当前状态不可达，跳过}// 遍历当前采样员的所有分配选项（0到4名志愿者）for(let volunteers = 0; volunteers <= 4; volunteers++){const cost = volunteers; // 当前分配方案需要的志愿者数量if(j + cost > V){continue; // 超过总志愿者数，跳过}let efficiency;if(volunteers === 0){efficiency = N[i] - 2 * M; // 无志愿者时效率下降}else{let extra = volunteers - 1; // 额外志愿者数量if(extra > 3){extra = 3; // 最多提升3M}efficiency = N[i] + extra * M; // 计算效率}// 更新dp_next数组if(dp[j] + efficiency > dp_next[j + cost]){dp_next[j + cost] = dp[j] + efficiency;}}}dp = dp_next; // 更新DP数组}// 寻找最大总效率let max_efficiency = Math.max(...dp);console.log(max_efficiency); // 输出结果
});

八、C算法源码

/* C语言版本 */#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>#define MAX_V 500int main(){int S, V; // 采样员人数和志愿者人数scanf("%d %d", &S, &V); // 读取S和Vint N[S]; // 采样员基准效率数组for(int i = 0; i < S; i++){scanf("%d", &N[i]); // 读取每个采样员的基准效率}// 初始化DP数组，长度为V+1，初始值为非常小的数long long dp[V+1];for(int i = 0; i <= V; i++){dp[i] = LLONG_MIN;}dp[0] = 0; // 无志愿者时，效率为0// 遍历每个采样员for(int i = 0; i < S; i++){int M = N[i] / 10; // 计算M_ilong long dp_next[V+1];for(int j = 0; j <= V; j++){dp_next[j] = LLONG_MIN; // 初始化新的DP数组}for(int j = 0; j <= V; j++){if(dp[j] == LLONG_MIN){continue; // 如果当前状态不可达，跳过}// 遍历当前采样员的所有分配选项（0到4名志愿者）for(int volunteers = 0; volunteers <=4; volunteers++){int cost = volunteers; // 当前分配方案需要的志愿者数量if(j + cost > V){continue; // 超过总志愿者数，跳过}long long efficiency;if(volunteers == 0){efficiency = (long long)N[i] - 2LL * M; // 无志愿者时效率下降}else{int extra = volunteers -1; // 额外志愿者数量if(extra > 3){extra = 3; // 最多提升3M}efficiency = (long long)N[i] + (long long)(extra) * M; // 计算效率}// 更新dp_next数组if(dp[j] + efficiency > dp_next[j + cost]){dp_next[j + cost] = dp[j] + efficiency;}}}// 将dp_next赋值回dpfor(int j = 0; j <= V; j++){dp[j] = dp_next[j];}}// 寻找最大总效率long long max_efficiency = LLONG_MIN;for(int i = 0; i <= V; i++){if(dp[i] > max_efficiency){max_efficiency = dp[i];}}printf("%lld\n", max_efficiency); // 输出结果return 0;
}

九、C++算法源码

// C++版本#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int S, V; // 采样员人数和志愿者人数cin >> S >> V; // 读取S和Vvector<int> N(S); // 采样员基准效率数组for(int i = 0; i < S; i++){cin >> N[i]; // 读取每个采样员的基准效率}// 初始化DP数组，长度为V+1，初始值为-无穷vector<long long> dp(V+1, LLONG_MIN);dp[0] = 0; // 无志愿者时，效率为0// 遍历每个采样员for(int i = 0; i < S; i++){int M = N[i] / 10; // 计算M_ivector<long long> dp_next(V+1, LLONG_MIN); // 创建新的DP数组for(int j = 0; j <= V; j++){if(dp[j] == LLONG_MIN){continue; // 如果当前状态不可达，跳过}// 遍历当前采样员的所有分配选项（0到4名志愿者）for(int volunteers = 0; volunteers <=4; volunteers++){int cost = volunteers; // 当前分配方案需要的志愿者数量if(j + cost > V){continue; // 超过总志愿者数，跳过}long long efficiency;if(volunteers == 0){efficiency = (long long)N[i] - 2LL * M; // 无志愿者时效率下降}else{int extra = volunteers -1; // 额外志愿者数量if(extra > 3){extra = 3; // 最多提升3M}efficiency = (long long)N[i] + (long long)(extra) * M; // 计算效率}// 更新dp_next数组dp_next[j + cost] = max(dp_next[j + cost], dp[j] + efficiency);}}dp = dp_next; // 更新DP数组}// 寻找最大总效率long long max_efficiency = LLONG_MIN;for(int i = 0; i <= V; i++){if(dp[i] > max_efficiency){max_efficiency = dp[i];}}cout << max_efficiency << "\n"; // 输出结果return 0;
}