华为OD机试：动态规划解决称砝码问题

1. 华为OD机试真题解析称砝码问题概述这道称砝码题目是华为ODHuawei Outsourcing Development机试中的经典考题之一主要考察应聘者对动态规划算法的掌握程度以及多语言编码能力。题目通常会给出若干不同重量的砝码和各砝码的数量要求计算出用这些砝码可以称出多少种不同的重量组合。在实际的华为OD机试环境中这道题目会以ACM模式呈现即需要从标准输入读取数据处理后输出到标准输出。题目难度属于中等偏上非常适合检验候选人的算法思维和编码基本功。根据网络上的考生反馈这道题在近两年的华为OD机试中出现频率较高特别是在C卷和部分B卷中。2. 问题分析与数学建模2.1 问题描述与示例假设我们有以下输入砝码种类数n3每种砝码的重量分别为1g、2g、3g对应的数量分别为2个、1个、1个那么所有可能的组合方式包括不使用任何砝码0g使用1g砝码1g1个、2g2个使用2g砝码2g使用3g砝码3g组合使用123g134g235g1124g1135g1236g去除重复后可以得到能够称出的不同重量为0,1,2,3,4,5,6共7种。2.2 数学模型建立这个问题可以转化为典型的背包问题变种。设砝码种类为n第i种砝码的重量为w[i]数量为c[i]。我们需要找出所有可能的重量组合其中每种砝码可以选择0到c[i]个。数学表达式为 S { sum(a_i * w_i) | 0 ≤ a_i ≤ c_i, 1 ≤ i ≤ n } ∪ {0}其中a_i表示第i种砝码选取的数量S表示所有可能的重量集合。3. 动态规划解法详解3.1 基本思路动态规划是解决此类组合问题的有效方法。我们可以定义一个布尔型数组dp其中dp[i]表示重量i是否可以被称出。初始时dp[0]true表示重量0总是可以称出即不使用任何砝码其余为false。然后对于每种砝码我们遍历所有可能的数量更新dp数组。具体步骤如下初始化dp[0]true其余为false对于每种砝码i重量为w数量为c a. 对于当前已经可以称出的重量j从大到小遍历 b. 对于该砝码的数量k从1到c c. 如果j kw不超过最大可能重量则设置dp[j kw] true最后统计dp数组中为true的元素个数3.2 算法优化上述基本方法存在重复计算的问题。更高效的实现是计算所有砝码总重量的上限max_weight sum(w[i]*c[i])初始化dp数组大小为max_weight1dp[0]true对于每种砝码i a. 逆序遍历dp数组从max_weight到0 b. 如果dp[j]为true则对于k从1到c[i]设置dp[j k*w[i]] true统计dp数组中true的个数这种方法的时间复杂度为O(n * max_weight * c_max)其中n是砝码种类数max_weight是总重量上限c_max是单种砝码的最大数量。4. 多语言实现代码4.1 C实现#include iostream #include vector #include unordered_set using namespace std; int main() { int n; cin n; vectorint weights(n); for(int i 0; i n; i) { cin weights[i]; } vectorint counts(n); for(int i 0; i n; i) { cin counts[i]; } unordered_setint result; result.insert(0); for(int i 0; i n; i) { unordered_setint temp(result); for(auto it temp.begin(); it ! temp.end(); it) { for(int j 1; j counts[i]; j) { result.insert(*it j * weights[i]); } } } cout result.size() endl; return 0; }4.2 Python实现n int(input()) weights list(map(int, input().split())) counts list(map(int, input().split())) result {0} for i in range(n): temp set(result) for w in temp: for j in range(1, counts[i]1): result.add(w j * weights[i]) print(len(result))4.3 Java实现import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); int[] weights new int[n]; for(int i 0; i n; i) { weights[i] scanner.nextInt(); } int[] counts new int[n]; for(int i 0; i n; i) { counts[i] scanner.nextInt(); } SetInteger result new HashSet(); result.add(0); for(int i 0; i n; i) { SetInteger temp new HashSet(result); for(int w : temp) { for(int j 1; j counts[i]; j) { result.add(w j * weights[i]); } } } System.out.println(result.size()); } }4.4 JavaScript实现const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let input []; rl.on(line, (line) { input.push(line); }).on(close, () { const n parseInt(input[0]); const weights input[1].split( ).map(Number); const counts input[2].split( ).map(Number); let result new Set(); result.add(0); for(let i 0; i n; i) { const temp new Set(result); for(const w of temp) { for(let j 1; j counts[i]; j) { result.add(w j * weights[i]); } } } console.log(result.size); });4.5 Go实现package main import ( bufio fmt os strconv strings ) func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() n, _ : strconv.Atoi(scanner.Text()) scanner.Scan() weightsStr : strings.Fields(scanner.Text()) weights : make([]int, n) for i : 0; i n; i { weights[i], _ strconv.Atoi(weightsStr[i]) } scanner.Scan() countsStr : strings.Fields(scanner.Text()) counts : make([]int, n) for i : 0; i n; i { counts[i], _ strconv.Atoi(countsStr[i]) } result : make(map[int]bool) result[0] true for i : 0; i n; i { temp : make(map[int]bool) for k : range result { temp[k] true } for w : range temp { for j : 1; j counts[i]; j { result[wj*weights[i]] true } } } fmt.Println(len(result)) }5. 算法优化与性能分析5.1 时间复杂度优化上述实现中我们使用了集合来存储结果这在实际应用中可能会带来一定的性能开销。更高效的实现可以使用位运算或布尔数组来优化int countWeights(vectorint weights, vectorint counts) { int max_weight 0; for(int i 0; i weights.size(); i) { max_weight weights[i] * counts[i]; } vectorbool dp(max_weight 1, false); dp[0] true; for(int i 0; i weights.size(); i) { for(int j max_weight; j 0; --j) { if(dp[j]) { for(int k 1; k counts[i]; k) { if(j k * weights[i] max_weight) { dp[j k * weights[i]] true; } } } } } return count(dp.begin(), dp.end(), true); }这种实现的时间复杂度为O(n * max_weight * c_max)空间复杂度为O(max_weight)。5.2 边界条件处理在实际编程中需要注意以下边界条件输入可能包含0重量或0数量的砝码需要过滤所有砝码数量为0的情况只能称出0大数量砝码情况下的性能问题可能需要进一步优化大重量砝码情况下的内存问题可能需要使用更紧凑的数据结构6. 华为OD机试实战技巧6.1 输入输出处理华为OD机试通常使用ACM模式需要特别注意输入输出格式多语言统一使用标准输入输出注意不同语言读取多行输入的方式输出格式必须严格符合题目要求注意处理可能的输入错误虽然测试用例通常规范6.2 调试技巧在机试环境中调试受限建议先在本地IDE中编写和测试代码准备一些测试用例包括边界情况使用打印语句调试关键变量注意不同语言的性能特性如Python可能比C慢6.3 代码风格建议虽然机试主要考察算法正确性但良好的代码风格有助于使用有意义的变量名适当添加注释说明关键步骤保持代码简洁避免冗余合理使用函数/方法分解复杂逻辑7. 常见问题与解决方案7.1 内存不足问题当砝码总重量很大时布尔数组可能占用过多内存。解决方案使用位压缩每个位表示一个重量使用更紧凑的数据结构分批处理砝码7.2 重复计算问题某些实现可能导致重复计算相同重量。解决方案使用集合自动去重优化遍历顺序如逆序遍历使用动态规划的经典背包问题优化技巧7.3 多语言实现差异不同语言在实现时需要注意集合操作API的差异输入输出性能差异默认数据结构的特性如Python的set比list快语言特有的优化技巧如C的位运算