中山网站优化_看2d影片最好的地方_网络营销步骤_北京seo薪资

2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

本文收录于专栏：《2025华为OD真题目录+全流程解析/备考攻略/经验分享》

华为OD机试真题《会议接待 /代表团坐车》：

---

---

题目名称：会议接待 /代表团坐车

---

• 知识点：动态规划（背包问题）
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团。为提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

约束条件：

1. 一个代表团只能上一辆车，且代表团人数（每个代表团人数≤30，总数量≤30）必须小于汽车容量（≤100）。
2. 必须将车辆坐满，即所选代表团人数总和等于汽车容量。

输入描述：

• 第一行为各代表团人数，以英文逗号分隔（如 5,4,2,3,2,4,9）。
• 第二行为汽车载客量（如 10）。

输出描述：

• 输出坐满汽车的方案数量，若无解则输出 0。

示例：
输入：

5,4,2,3,2,4,9  
10  

输出：

4  

说明：
可能的组合为 [2,3,5]、[2,4,4]、[2,3,5]、[2,4,4]（允许重复选择不同索引的相同数值代表团，但每个代表团仅能被选一次）。

补充说明：

• 代表团人数按输入顺序排列，组合需严格满足总和等于汽车容量。
• 动态规划（背包问题）或回溯法为典型解法。

---

Java

问题分析

我们需要计算从代表团中选择若干代表团，使其人数之和等于汽车的容量，且每个代表团只能被选一次。这是一个典型的0-1背包问题，要求恰好装满背包的方案数。

---

解题思路

1. 动态规划定义：
   • dp[j] 表示总和为 j 的方案数。
2. 状态转移：
   • 遍历每个代表团人数 num，从后向前更新 dp[j]：dp[j] += dp[j - num]。
3. 初始化：
   • dp[0] = 1，表示总和为0的方案数为1（不选任何代表团）。

---

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取代表团人数String[] parts = scanner.nextLine().split(",");int[] nums = new int[parts.length];for (int i = 0; i < parts.length; i++) {nums[i] = Integer.parseInt(parts[i]);}// 读取汽车容量int capacity = Integer.parseInt(scanner.nextLine());int[] dp = new int[capacity + 1];dp[0] = 1; // 初始化：总和为0的方案数为1（不选任何代表团）// 动态规划处理每个代表团人数for (int num : nums) {// 从后向前遍历，确保每个代表团只被选一次for (int j = capacity; j >= num; j--) {dp[j] += dp[j - num];}}// 输出结果System.out.println(dp[capacity]);}
}

---

代码详细解析

1. 输入处理：

   • 使用 Scanner 读取输入，将代表团人数分割为整数数组 nums。
   • 读取汽车容量 capacity。

2. 动态规划数组初始化：

   • dp 数组长度为 capacity + 1，初始时 dp[0] = 1，其余为0。

3. 遍历每个代表团人数：

   • 对每个 num，从 capacity 到 num 逆序遍历，更新 dp[j]：

     for (int j = capacity; j >= num; j--) {dp[j] += dp[j - num];
     }
     

   • 逆序遍历确保每个代表团仅被考虑一次（0-1背包特性）。

4. 输出结果：

   • dp[capacity] 存储了恰好装满汽车的方案数。

---

示例测试

示例1输入：

5,4,2,3,2,4,9  
10  

输出：

4  

解析：
可能的组合为：

• 5（索引0）、2（索引2）、3（索引3）
• 4（索引1）、4（索引5）、2（索引4）
• 5（索引0）、2（索引4）、3（索引3）
• 4（索引1）、4（索引5）、2（索引2）

示例2输入：

2,2  
4  

输出：

1  

解析：
唯一方案：选择两个2（不同索引）。

示例3输入：

1,1,1  
3  

输出：

1  

解析：
唯一方案：选择所有三个1。

---

综合分析

1. 时间复杂度：O(N×C)

   • N 为代表团数量，C 为汽车容量。每个代表团需遍历 C 次。

2. 空间复杂度：O©

   • 仅需一个长度为 C+1 的数组。

3. 优势：

   • 高效准确：动态规划严格保证最优解。
   • 空间优化：一维数组节省内存。
   • 处理大容量：使用 int 数组避免溢出（假设结果在 int 范围内）。

4. 适用场景：

   • 代表团数量较大（如 N=30），汽车容量适中（如 C=100）。

---

python

问题分析

我们需要从代表团中选择若干代表团，使它们的人数之和等于汽车容量，且每个代表团只能被选一次。这是一个典型的0-1背包问题，要求恰好装满背包的方案数。

---

解题思路

1. 动态规划定义：
   • dp[j] 表示总和为 j 的方案数。
2. 状态转移：
   • 遍历每个代表团人数 num，从后向前更新 dp[j]：dp[j] += dp[j - num]。
3. 初始化：
   • dp[0] = 1，表示总和为0的方案数为1（不选任何代表团）。

---

代码实现

def main():import sys# 读取输入input_lines = sys.stdin.read().splitlines()nums = list(map(int, input_lines[0].split(',')))capacity = int(input_lines[1])# 初始化动态规划数组dp = [0] * (capacity + 1)dp[0] = 1  # 总和为0的方案数为1# 处理每个代表团人数for num in nums:# 从后向前遍历，确保每个代表团只被选一次for j in range(capacity, num - 1, -1):if j >= num:dp[j] += dp[j - num]# 输出结果print(dp[capacity])if __name__ == "__main__":main()

---

代码详细解析

1. 输入处理：

   • input_lines[0] 读取代表团人数并转换为整数列表 nums。
   • input_lines[1] 读取汽车容量 capacity。

2. 初始化动态规划数组：

   • dp 数组长度为 capacity + 1，初始时 dp[0] = 1，其余为0。

3. 遍历每个代表团人数：

   • 对每个 num，从 capacity 到 num 逆序遍历，更新 dp[j]：

     for j in range(capacity, num - 1, -1):if j >= num:dp[j] += dp[j - num]
     

   • 逆序遍历确保每个代表团仅被考虑一次（0-1背包特性）。

4. 输出结果：

   • dp[capacity] 存储了恰好装满汽车的方案数。

---

示例测试

示例1输入：

5,4,2,3,2,4,9  
10  

输出：

4  

解析：
可能的组合为：

• 5（索引0）、2（索引2）、3（索引3）
• 4（索引1）、4（索引5）、2（索引4）
• 5（索引0）、2（索引4）、3（索引3）
• 4（索引1）、4（索引5）、2（索引2）

示例2输入：

2,2  
4  

输出：

1  

解析：
唯一方案：选择两个2（不同索引）。

示例3输入：

1,1,1  
3  

输出：

1  

解析：
唯一方案：选择所有三个1。

---

综合分析

1. 时间复杂度：O(N×C)

   • N 为代表团数量，C 为汽车容量。每个代表团需遍历 C 次。

2. 空间复杂度：O©

   • 仅需一个长度为 C+1 的数组。

3. 优势：

   • 高效准确：动态规划严格保证最优解。
   • 空间优化：一维数组节省内存。
   • 处理大容量：使用 int 数组避免溢出（假设结果在 int 范围内）。

4. 适用场景：

   • 代表团数量较大（如 N=30），汽车容量适中（如 C=100）。

---

JavaScript

问题分析

我们需要从代表团中选择若干代表团，使它们的人数之和恰好等于汽车容量，且每个代表团只能被选一次。这是0-1背包问题的变种，要求计算恰好装满背包的方案数。

---

解题思路

1. 动态规划定义：
   • dp[j] 表示总和为 j 的方案数。
2. 状态转移：
   • 遍历每个代表团人数 num，从后向前更新 dp[j]：dp[j] += dp[j - num]。
3. 初始化：
   • dp[0] = 1，表示总和为0的方案数为1（不选任何代表团）。

---

代码实现

const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false,
});let lines = [];
rl.on("line", (line) => {lines.push(line.trim());
});rl.on("close", () => {// 解析输入数据const nums = lines[0].split(",").map(Number); // 代表团人数数组const capacity = parseInt(lines[1], 10);       // 汽车容量// 初始化动态规划数组const dp = new Array(capacity + 1).fill(0);dp[0] = 1; // 总和为0的方案数为1（空方案）// 处理每个代表团人数for (const num of nums) {// 逆序遍历容量，确保每个代表团只被选一次for (let j = capacity; j >= num; j--) {dp[j] += dp[j - num];}}// 输出结果console.log(dp[capacity]);
});

---

代码详细解析

1. 输入处理：

   • readline 逐行读取输入，存入 lines 数组。
   • lines[0] 解析为代表团人数数组，lines[1] 解析为汽车容量。

2. 初始化动态规划数组：

   const dp = new Array(capacity + 1).fill(0);
   dp[0] = 1;
   

   • 数组长度为 capacity + 1，初始值全为0，dp[0] 设为1。

3. 动态规划核心逻辑：

   for (const num of nums) {for (let j = capacity; j >= num; j--) {dp[j] += dp[j - num];}
   }
   

   • 逆序遍历：确保每个代表团只被使用一次（0-1背包特性）。
   • 状态转移：当前容量 j 的方案数加上 j - num 的方案数。

4. 输出结果：

   • dp[capacity] 存储了恰好装满汽车的方案数。

---

示例测试

示例1输入：

5,4,2,3,2,4,9  
10  

输出：

4  

解析：
可能的组合为：

• 5（索引0）、2（索引2）、3（索引3）
• 4（索引1）、4（索引5）、2（索引4）
• 5（索引0）、2（索引4）、3（索引3）
• 4（索引1）、4（索引5）、2（索引2）

示例2输入：

2,2  
4  

输出：

1  

解析：
唯一方案：选择两个不同索引的2。

示例3输入：

1,1,1  
3  

输出：

1  

解析：
唯一方案：选择所有三个1。

---

综合分析

1. 时间复杂度：O(N×C)

   • N 为代表团数量，C 为汽车容量。每个代表团需遍历 C 次。

2. 空间复杂度：O©

   • 仅需一个长度为 C+1 的数组。

3. 优势：

   • 高效准确：动态规划严格保证计算所有可能方案。
   • 空间优化：一维数组节省内存。
   • 逻辑清晰：代码简洁，直接体现背包问题核心逻辑。

4. 适用场景：

   • 代表团数量较大（例如30个）且容量适中（例如100）的场景。

---

C++

问题分析

我们需要从代表团中选择若干代表团，使它们的人数之和恰好等于汽车容量，且每个代表团只能被选一次。这是一个经典的0-1背包问题，要求计算恰好装满背包的方案数。

---

解题思路

1. 动态规划定义：
   • dp[j] 表示总和为 j 的方案数。
2. 状态转移：
   • 遍历每个代表团人数 num，从后向前更新 dp[j]：dp[j] += dp[j - num]。
3. 初始化：
   • dp[0] = 1，表示总和为0的方案数为1（不选任何代表团）。

---

代码实现

#include <iostream>
#include <vector>
#include <sstream>
#include <string>using namespace std;int main() {// 读取输入string nums_str;getline(cin, nums_str);int capacity;cin >> capacity;// 将逗号分隔的字符串转换为数组vector<int> nums;stringstream ss(nums_str);string token;while (getline(ss, token, ',')) {nums.push_back(stoi(token));}// 初始化动态规划数组vector<int> dp(capacity + 1, 0);dp[0] = 1; // 空集的方案数为1// 处理每个代表团人数for (int num : nums) {// 逆序遍历容量，确保每个代表团只被选一次for (int j = capacity; j >= num; j--) {dp[j] += dp[j - num];}}// 输出结果cout << dp[capacity] << endl;return 0;
}

---

代码详细解析

1. 输入处理

string nums_str;
getline(cin, nums_str);       // 读取代表团人数行（如 "5,4,2,3,2"）
int capacity;
cin >> capacity;              // 读取汽车容量

• 第一行输入通过 getline 读取为字符串，第二行通过 cin 直接读取整数。

2. 字符串分割

vector<int> nums;
stringstream ss(nums_str);    // 将字符串转为流
string token;
while (getline(ss, token, ',')) {nums.push_back(stoi(token)); // 按逗号分割并转为整数
}

• 使用 stringstream 和 getline 分割逗号分隔的字符串，逐个转为整数存入数组。

3. 动态规划数组初始化

vector<int> dp(capacity + 1, 0);
dp[0] = 1; // 总和为0的方案数为1

• 创建长度为 capacity + 1 的数组，初始值全为0，dp[0] 设为1。

4. 动态规划核心逻辑

for (int num : nums) {for (int j = capacity; j >= num; j--) {dp[j] += dp[j - num];}
}

• 逆序遍历容量：确保每个代表团只被使用一次（0-1背包特性）。
• 状态转移：当前容量 j 的方案数加上 j - num 的方案数。

5. 输出结果

cout << dp[capacity] << endl;

• dp[capacity] 存储恰好装满汽车的方案数。

---

示例测试

示例1输入：

5,4,2,3,2,4,9
10

输出：

4

解析：
可能的组合为：

• 5（索引0）+2（索引2）+3（索引3）
• 4（索引1）+4（索引5）+2（索引4）
• 5（索引0）+2（索引4）+3（索引3）
• 4（索引1）+4（索引5）+2（索引2）

示例2输入：

2,2
4

输出：

1

解析：
唯一方案：选择两个不同索引的 2。

示例3输入：

1,1,1
3

输出：

1

解析：
唯一方案：选择所有三个 1。

---

综合分析

1. 时间复杂度：O(N×C)

   • N 为代表团数量，C 为汽车容量。每个代表团需遍历 C 次。

2. 空间复杂度：O©

   • 仅需一个长度为 C+1 的数组，与代表团数量无关。

3. 优势：

   • 严格正确性：动态规划确保计算所有可能的方案。
   • 空间高效：一维数组优化内存使用。
   • 输入处理灵活：支持任意数量的代表团输入。

4. 适用场景：

   • 代表团数量较大（例如 N=30）且容量适中（例如 C=100）的场景。

---

C语言

问题分析

我们需要从代表团中选择若干代表团，使其人数之和恰好等于汽车容量，每个代表团只能被选一次。这是0-1背包问题的变种，要求计算恰好装满背包的方案数。

---

解题思路

1. 动态规划定义：
   • dp[j] 表示总和为 j 的方案数。
2. 状态转移：
   • 遍历每个代表团人数 num，从后向前更新 dp[j]：dp[j] += dp[j - num]。
3. 初始化：
   • dp[0] = 1，表示总和为0的方案数为1（不选任何代表团）。

---

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int main() {char line[1000];fgets(line, sizeof(line), stdin);  // 读取代表团人数行int capacity;scanf("%d", &capacity);            // 读取汽车容量int nums[30];       // 存储代表团人数（最多30个）int count = 0;      // 代表团数量// 分割逗号分隔的字符串char *token = strtok(line, ",\n");while (token != NULL && count < 30) {nums[count++] = atoi(token);token = strtok(NULL, ",\n");}int dp[101] = {0};  // 容量最大为100，初始化dp数组dp[0] = 1;          // 初始状态：总和为0的方案数为1// 动态规划处理每个代表团人数for (int i = 0; i < count; i++) {int num = nums[i];// 逆序遍历容量，避免重复选择同一代表团for (int j = capacity; j >= num; j--) {dp[j] += dp[j - num];}}printf("%d\n", dp[capacity]);return 0;
}

---

代码详细解析

1. 输入处理：

   • fgets 读取代表团人数行，存入字符串 line。
   • scanf 读取汽车容量 capacity。
   • strtok 分割逗号分隔的字符串，转换为整数存入 nums 数组。

2. 动态规划数组初始化：

   • int dp[101] = {0}：创建长度为 capacity + 1 的数组，初始化为0。
   • dp[0] = 1：总和为0的方案数为1（不选任何代表团）。

3. 动态规划核心逻辑：

   for (int i = 0; i < count; i++) {int num = nums[i];for (int j = capacity; j >= num; j--) {dp[j] += dp[j - num];}
   }
   

   • 逆序遍历容量：确保每个代表团仅被使用一次。
   • 状态转移：当前容量 j 的方案数加上 j - num 的方案数。

4. 输出结果：

   • dp[capacity] 存储恰好装满汽车的方案数。

---

示例测试

示例1输入：

5,4,2,3,2,4,9  
10  

输出：

4  

解析：
可能的组合为：

• 5（索引0）、2（索引2）、3（索引3）
• 4（索引1）、4（索引5）、2（索引4）
• 5（索引0）、2（索引4）、3（索引3）
• 4（索引1）、4（索引5）、2（索引2）

示例2输入：

2,2  
4  

输出：

1  

解析：
唯一方案：选择两个不同索引的2。

示例3输入：

1,1,1  
3  

输出：

1  

解析：
唯一方案：选择所有三个1。

---

综合分析

1. 时间复杂度：O(N×C)

   • N 为代表团数量，C 为汽车容量。每个代表团需遍历 C 次。

2. 空间复杂度：O©

   • 仅需一个长度为 C+1 的数组，内存占用极低。

3. 优势：

   • 高效准确：动态规划严格计算所有可能方案。
   • 空间优化：一维数组节省内存。
   • 逻辑简洁：代码直观体现0-1背包核心逻辑。

4. 适用场景：

   • 代表团数量较大（例如30个）且容量适中（例如100）的场景。

---

GO

问题分析

我们需要从代表团中选择若干代表团，使其人数之和恰好等于汽车容量，且每个代表团只能被选一次。这是典型的0-1背包问题，要求计算恰好装满背包的方案数。

---

解题思路

1. 动态规划定义：
   • dp[j] 表示总和为 j 的方案数。
2. 状态转移：
   • 遍历每个代表团人数 num，从后向前更新 dp[j]：dp[j] += dp[j - num]。
3. 初始化：
   • dp[0] = 1，表示总和为0的方案数为1（不选任何代表团）。

---

代码实现

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()numsLine := scanner.Text()            // 读取代表团人数行scanner.Scan()capacity, _ := strconv.Atoi(scanner.Text()) // 读取汽车容量// 将逗号分隔的字符串转换为整数数组numsStr := strings.Split(numsLine, ",")nums := make([]int, len(numsStr))for i, s := range numsStr {nums[i], _ = strconv.Atoi(s)}// 初始化动态规划数组dp := make([]int, capacity+1)dp[0] = 1 // 空集的方案数为1// 处理每个代表团人数for _, num := range nums {// 逆序遍历容量，确保每个代表团只被选一次for j := capacity; j >= num; j-- {dp[j] += dp[j - num]}}// 输出结果fmt.Println(dp[capacity])
}

---

代码详细解析

1. 输入处理：

   • bufio.Scanner 读取输入，第一行是逗号分隔的代表团人数，第二行是汽车容量。
   • strings.Split 分割字符串为字符串数组，再逐个转为整数数组 nums。

2. 动态规划数组初始化：

   • dp := make([]int, capacity+1) 创建长度为 capacity + 1 的切片。
   • dp[0] = 1 表示总和为0的方案数为1。

3. 动态规划核心逻辑：

   • 遍历每个代表团人数 num：

     for j := capacity; j >= num; j-- {dp[j] += dp[j - num]
     }
     

   • 逆序遍历：确保每个代表团仅被使用一次（0-1背包特性）。
   • 状态转移：当前容量 j 的方案数加上 j - num 的方案数。

4. 输出结果：

   • dp[capacity] 存储恰好装满汽车的方案数。

---

示例测试

示例1输入：

5,4,2,3,2,4,9  
10  

输出：

4  

解析：
可能的组合为：

• 5（索引0）+2（索引2）+3（索引3）
• 4（索引1）+4（索引5）+2（索引4）
• 5（索引0）+2（索引4）+3（索引3）
• 4（索引1）+4（索引5）+2（索引2）

示例2输入：

2,2  
4  

输出：

1  

解析：
唯一方案：选择两个不同索引的 2。

示例3输入：

1,1,1  
3  

输出：

1  

解析：
唯一方案：选择所有三个 1。

---

综合分析

1. 时间复杂度：O(N×C)

   • N 为代表团数量，C 为汽车容量。每个代表团需遍历 C 次。

2. 空间复杂度：O©

   • 仅需一个长度为 C+1 的切片，内存占用极低。

3. 优势：

   • 严格正确性：动态规划保证计算所有可能的方案。
   • 空间高效：一维数组优化内存使用。
   • 输入处理简洁：Go的字符串操作库简化输入解析。

4. 适用场景：

   • 代表团数量较大（例如30个）且容量适中（例如100）的场景。

---

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！