1. 问题背景与需求分析称砝码是华为机考中一道经典的动态规划问题主要考察候选人对组合数学和算法设计的理解能力。题目通常给出n种不同重量的砝码每种砝码有若干个要求计算出这些砝码能够称出的所有不同重量组合。这类问题在实际工程中有广泛的应用场景物流领域的货物称重组合计算金融投资中的资产组合配置工业生产中的原料配比方案游戏开发中的装备属性组合系统2. 问题建模与数学原理2.1 问题形式化描述给定n种砝码重量分别为w₁,w₂,...,wₙ每种砝码的数量分别为m₁,m₂,...,mₙ求这些砝码能称出的所有不同重量的总数2.2 组合数学基础这是一个典型的多重集组合问题。我们需要计算的是所有可能的非负整数解(x₁,x₂,...,xₙ)其中0≤xᵢ≤mᵢ使得w₁x₁ w₂x₂ ... wₙxₙ W其中W就是可以称出的重量。3. 动态规划解决方案3.1 基本思路使用动态规划来解决这个问题的核心思想是定义一个布尔型数组dp其中dp[i]表示能否称出重量i初始时dp[0] true重量0总是可以称出对于每种砝码更新dp数组3.2 算法实现步骤def count_weights(weights, counts): max_weight sum(w * c for w, c in zip(weights, counts)) dp [False] * (max_weight 1) dp[0] True for w, c in zip(weights, counts): for i in range(max_weight, -1, -1): if dp[i]: for k in range(1, c 1): if i w * k max_weight: dp[i w * k] True return sum(dp)3.3 复杂度分析时间复杂度O(n × W × max_count)空间复杂度O(W)其中n是砝码种类数W是最大可能重量max_count是单个砝码的最大数量。4. 优化策略与技巧4.1 空间优化可以使用位运算来优化空间def count_weights_optimized(weights, counts): dp 1 # 用二进制位表示最低位代表重量0 for w, c in zip(weights, counts): new_dp dp for _ in range(c): new_dp | (new_dp w) dp new_dp return bin(dp).count(1)4.2 剪枝策略提前计算最大可能重量对砝码按重量排序先处理大砝码合并相同重量的砝码5. 边界条件与测试用例5.1 常见边界情况只有一种砝码所有砝码重量相同砝码数量为1砝码重量为15.2 测试用例示例test_cases [ # (weights, counts, expected) ([1], [1], 2), # 0,1 ([1,2], [2,1], 4), # 0,1,2,3 ([1,2,3], [1,1,1], 7) # 0,1,2,3,4,5,6 ]6. 实际编码注意事项输入处理注意题目给出的输入格式可能是字符串需要解析输出要求确认是返回数量还是所有可能的重量数据类型注意大数情况下的整数溢出问题性能优化对于大规模数据需要考虑更高效的算法7. 类似问题扩展硬币找零问题背包问题变种子集和问题组合数计算问题8. 华为机考特点分析通常要求处理大规模数据需要完整的输入输出处理注重代码的鲁棒性和边界处理时间限制严格需要优化算法9. 个人实战经验分享在实际编码中我发现以下几点特别重要先写伪代码理清思路处理边界条件要仔细使用print调试中间结果注意变量命名清晰预留足够时间测试对于这个具体问题最容易出错的地方是忘记初始化dp[0]True内层循环方向错误应该从大到小没有考虑砝码数量限制输出结果包含0的情况处理10. 进阶学习建议深入理解动态规划原理练习LeetCode相关题目学习数学组合知识研究算法优化技巧多参加编程竞赛积累经验