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(