华为OD机试C卷：0/1背包动态规划解充电设备组合问题

1. 项目概述与核心需求解析最近在准备华为OD机试C卷的同学估计不少人都刷到了“查找充电设备组合”这道题。这道题在各大论坛和备考群里的讨论热度一直不低因为它完美地融合了基础的算法思想和实际的工程应用场景属于那种“看起来简单但想拿满分需要仔细琢磨”的典型题目。题目大意是给你一个充电设备功率数组和一个目标功率值需要从数组中找出一个组合使得其总功率最接近目标值但不能超过它。这本质上是一个0/1背包问题的变种或者更具体地说是“最接近目标值的子集和”问题。在机试的紧张环境下如何快速、准确地用Java实现并且处理好各种边界情况是区分普通通过和高分的关键。这道题的价值在于它不仅仅是一道算法题。在实际的软件开发中类似的场景比比皆是资源分配、预算规划、负载均衡等核心逻辑都是在一组约束条件下寻找最优或最接近最优的解。因此吃透这道题掌握其背后的动态规划思想对于提升解决实际问题的能力大有裨益。无论你是正在备战华为OD还是想巩固自己的Java算法功底这篇从思路推导到代码实现再到踩坑经验的全方位解析都应该能给你带来直接的帮助。2. 问题本质与算法思路拆解2.1 问题重述与抽象建模我们先抛开“充电设备”这个业务外壳把问题抽象成一个纯粹的算法模型输入一个正整数数组int[] powers代表每个设备的功率一个正整数int target代表充电站的最大输出功率目标值。输出一个整数代表所选设备功率之和。这个和必须满足两个条件1) 小于等于target2) 在所有可能的组合中与target的差值最小。核心约束每个设备最多只能被选择一次0/1选择。这立刻让我们联想到经典的0/1背包问题。在背包问题中我们有物品的重量和价值背包有容量限制目标是让背包内物品的总价值最大。在这里我们可以做一个巧妙的映射设备功率同时扮演了“物品重量”和“物品价值”的角色。目标功率target就是“背包容量”。我们的目标不再是最大化价值而是让“重量”也就是功率和尽可能大但不能超过容量。因为“重量”和“价值”是同一个数所以“重量”最大即“价值”最大。这样一来问题就转化为了在总重量不超过背包容量的前提下尽可能装满背包。背包最后装了多少重量就是我们要的答案。2.2 动态规划方案选型与论证对于这类组合优化问题常见的思路有回溯DFS、枚举和动态规划DP。回溯/DFS思路直观通过递归遍历所有可能的组合。但其时间复杂度是指数级的O(2^n)当设备数量n稍大比如超过30时运行时间会急剧膨胀在机试的时限内几乎必然超时。因此除非数据规模特别小否则不予考虑。动态规划DP这是解决此问题的标准且高效的方法。其核心思想是“空间换时间”将大问题分解为重叠的子问题并存储子问题的解以避免重复计算。为什么DP适合0/1背包问题具有最优子结构性质。即考虑前i个设备、容量为j的背包的最优解可以由前i-1个设备的子问题推导出来。这正好契合DP的解题模式。DP的优势时间复杂度为O(n * target)其中n是设备数量。在机试常见的数据范围内n通常在100以内target在1000以内这个复杂度是完全可接受的能够保证稳定运行。基于以上分析我们确定采用动态规划作为本题的解决方案。下面我们将深入DP的状态定义、转移方程和具体实现细节。3. 动态规划实现详解与Java代码3.1 DP状态定义与数组设计我们定义一个二维的布尔数组或者整型数组但布尔型更直观dp[i][j]。i的含义考虑前i个充电设备即powers数组下标从0到i-1的设备。j的含义当前背包的容量即目标功率值。dp[i][j]的值一个布尔值表示是否能够从前i个设备中选出一些设备使得它们的总功率恰好等于j。这里有两个关键点需要理解“恰好等于” vs “不超过”我们定义的是“恰好等于”。为什么因为最终我们要找的是最接近target且不超过它的值。如果我们能知道所有“恰好等于”某个功率值j的可能性dp[i][j] true那么只要从target开始向下遍历j第一个遇到的dp[n][j]为true的j就是我们要找的答案。这比直接处理“不超过”要更清晰。数组大小dp数组的长度应该是[n1][target1]。i从0到nj从0到target。dp[0][0] true表示不考虑任何设备时功率和恰好为0是可能的一个空组合。3.2 状态转移方程推导状态转移是DP的核心它描述了如何从已知的小问题解出大问题的解。对于第i个设备其功率为power powers[i-1]注意下标对应关系在面对容量j时我们有两种选择不选择这个设备那么能否凑出功率j就完全取决于前i-1个设备了。即dp[i][j] dp[i-1][j]。选择这个设备前提是这个设备的功率power不能大于当前容量j。如果选择了它那么剩下的容量j - power就需要由前i-1个设备来凑出。即dp[i][j] dp[i-1][j - power]。由于我们的目标是“能否凑出”只要以上两种选择中有一种能成功那么dp[i][j]就是可行的。因此状态转移方程为dp[i][j] dp[i-1][j] || (j power dp[i-1][j - power])这个方程的意思是dp[i][j]为真要么是因为不选第i个设备就能凑出j要么是因为选了第i个设备后前i-1个设备能凑出j - power。3.3 完整Java代码实现与逐行解析理解了状态定义和转移方程我们就可以动手写代码了。以下是完整的、带有详细注释的Java实现。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取设备数量根据题目输入格式有时第一行是设备数量有时直接是数组这里假设第一行是数组 // 更通用的方式是直接读取一行按空格分割。这里根据常见题型调整。 String[] powerStrs scanner.nextLine().split( ); int n powerStrs.length; int[] powers new int[n]; for (int i 0; i n; i) { powers[i] Integer.parseInt(powerStrs[i]); } // 读取目标功率 int target scanner.nextInt(); scanner.close(); // 调用核心解题函数 int result findClosestCombination(powers, target); System.out.println(result); } /** * 查找最接近目标值的充电设备组合功率和 * param powers 充电设备功率数组 * param target 目标功率值 * return 最接近且不超过target的功率和 */ public static int findClosestCombination(int[] powers, int target) { int n powers.length; // 1. 创建DP表。dp[i][j] 表示前i个设备能否恰好组成功率j boolean[][] dp new boolean[n 1][target 1]; // 2. 初始化基础状态 // 前0个设备即没有设备可以组成功率0 dp[0][0] true; // 对于其他任何大于0的功率j前0个设备都无法组成boolean数组默认就是false无需显式设置。 // 3. 动态规划填表过程 for (int i 1; i n; i) { int power powers[i - 1]; // 当前设备的功率 for (int j 0; j target; j) { // 情况一不选当前设备 if (dp[i - 1][j]) { dp[i][j] true; } // 情况二选当前设备前提是当前设备功率不超过当前目标j // 注意这里用的是“或等”因为情况一可能已经将其设为true if (j power dp[i - 1][j - power]) { dp[i][j] true; } // 如果以上两种情况都不满足dp[i][j]保持默认的false } } // 4. 寻找答案从target开始向下遍历找到第一个dp[n][j]为true的j for (int j target; j 0; j--) { if (dp[n][j]) { return j; } } // 理论上dp[n][0]一定为true全不选所以这里不会走到但为了代码完整性返回0 return 0; } }代码关键点解析输入处理代码展示了两种常见的输入格式处理方式。实际考试中务必仔细阅读题目中的输入描述它可能是数组长度数组也可能是直接一行数组。这里是按“一行空格分隔的数字为数组”来处理的更具通用性。DP数组初始化dp[0][0] true是动态规划的“起点”代表空集合的和为0。这个初始化至关重要。填表顺序外层循环遍历设备i从1到n内层循环遍历所有可能的功率值j从0到target。这是标准的0/1背包填表顺序。答案查找填表完成后dp[n][j]就代表了考虑所有n个设备时能否凑出恰好为j的功率。我们从target开始向下查找第一个为true的j就是最接近且不超过目标的最大功率和。空间复杂度优化提示上面的代码使用了O(n*target)的空间。实际上观察状态转移方程dp[i][j]只依赖于dp[i-1][...]我们可以用一维数组dp[j]来优化空间将空间复杂度降至O(target)。这在target很大时能节省不少内存。优化后的内层循环需要从target到power逆序遍历以避免状态被覆盖。这是背包问题的一个经典优化技巧。4. 空间优化技巧与变种实现4.1 滚动数组优化一维DP对于机试而言在确保正确性的前提下写出空间优化的代码往往能体现更好的功底。下面给出空间优化后的版本。public static int findClosestCombinationOptimized(int[] powers, int target) { int n powers.length; // 使用一维DP数组dp[j]表示能否用已经遍历过的设备恰好组成功率j boolean[] dp new boolean[target 1]; // 初始化功率0总是可以达到不选任何设备 dp[0] true; // 遍历每个设备 for (int i 0; i n; i) { int power powers[i]; // 关键内层循环必须从大到小遍历 // 如果从小到大遍历同一个设备可能会被重复使用多次变成了完全背包问题。 for (int j target; j power; j--) { // 状态转移dp[j] dp[j] || dp[j - power] // 含义当前能组成j要么是之前就能组成j不选当前设备 // 要么是之前能组成j-power选了当前设备。 if (dp[j - power]) { dp[j] true; } // 如果dp[j]原本就是true这里不需要改动所以用if判断而非直接赋值 } } // 查找结果从target向下找到第一个为true的j for (int j target; j 0; j--) { if (dp[j]) { return j; } } return 0; }注意一维DP的内层逆序循环是绝对关键点。如果写成for (int j power; j target; j)就变成了完全背包每个设备无限使用结果将是错误的。务必理解并记住这个区别。4.2 处理特殊边界情况与异常输入一个健壮的程序必须考虑边界情况。在机试中这些细节可能就是那关键的几分。空数组输入如果powers数组为空无论target是多少答案都应该是0。我们的代码中n0DP初始化后直接进入查找循环dp[0]true会返回0结果是正确的。目标功率为0如果target为0那么任何功率大于0的设备都不能选答案只能是0。我们的代码中DP数组大小为1target11只有dp[0]初始化即为true查找时会直接返回0。设备功率超过目标值在动态规划过程中当j power时“选择当前设备”的情况会被跳过因为j power的条件不满足逻辑是正确的。输入包含非正整数题目通常保证输入是正整数。如果存在0或负数需要根据题意特殊处理。例如功率为0的设备选不选都不影响总和可能需要额外逻辑。5. 实战调试、常见“坑点”与心得5.1 调试方法与测试用例设计自己实现代码后不要只看样例。设计全面的测试用例是保证代码正确的唯一途径。推荐测试用例集// 测试用例1: 基础功能 输入: powers [1, 2, 3, 4, 5], target 10 输出: 10 (可以刚好凑满) // 测试用例2: 无法刚好凑满 输入: powers [2, 3, 5], target 7 输出: 6 (选择2和3无法凑出7) // 测试用例3: 目标值很小 输入: powers [10, 20, 30], target 5 输出: 0 (任何设备都超过目标值) // 测试用例4: 空数组或目标为0 输入: powers [], target 100 输出: 0 输入: powers [1,2,3], target 0 输出: 0 // 测试用例5: 大数测试检查数组越界和性能 输入: powers [50, 50, 50, ... 20个], target 1000 // 应能快速计算出结果 // 测试用例6: 包含重复功率 输入: powers [5, 5, 5, 8], target 14 输出: 13 (58)在本地IDE如IntelliJ IDEA, Eclipse或在线编程平台运行这些测试确保全部通过。5.2 机试中常见错误与避坑指南根据很多同学的反馈这道题容易在以下几个地方失分DP数组初始化错误忘记设置dp[0][0] true导致整个DP表结果全为false最终输出0。这是最经典的错误。数组下标越界在状态转移dp[i-1][j-power]时没有检查j power就访问数组导致当j power时访问dp[i-1][负数]而崩溃。一维DP遍历顺序错误如前所述使用一维数组优化时内层循环必须从大到小遍历。写成从小到大是高频错误。结果查找逻辑错误填完DP表后不是从target向下找而是向上找或乱找。题目要求是“不超过目标的最大值”所以必须从target开始递减查找。输入格式处理不当华为OD的机试系统输入通常是标准的Scanner或BufferedReader读取。务必看清题目输入说明是一行数字用空格隔开还是先读数量再读数组。处理不当会导致后续计算全部错误。时间或内存超限如果使用未优化的二维DP且target很大比如10^5可能会导致内存超出限制O(n*target)的布尔数组可能很大。这时应考虑使用一维DP优化空间。虽然C卷此题target通常不会过大但养成优化习惯是好的。5.3 个人实操心得与技巧先写二维再优化一维在考场上如果时间紧张优先保证写出正确清晰的二维DP代码。它逻辑更直观不易出错。如果时间充裕再改写成优化的一维版本作为加分项。善用打印调试在本地练习时对于小样例如powers[2,3], target5可以把整个DP表打印出来对照手动推导的结果这是理解DP过程最快的方式。// 调试打印示例 for (int i 0; i n; i) { for (int j 0; j target; j) { System.out.print((dp[i][j] ? T : F) ); } System.out.println(); }理解大于记忆不要死记硬背代码模板。务必理解dp[i][j]状态的定义以及“不选”和“选”两种决策如何导致状态转移。理解了本质即使题目稍有变化比如求方案数、求具体方案你也能灵活应对。关于“恰好装满”本题解法的精髓在于定义“恰好等于 j”。有些背包问题初始化时会将dp[0][j](j0) 设为负无穷来表示“不可能恰好装满”但本题我们只关心布尔状态且最终通过反向查找来满足“不超过”所以用“恰好装满”的定义配合查找是最清晰的思路。这道“查找充电设备组合”题就像一把钥匙帮你打开了用动态规划解决组合优化问题的大门。掌握它不仅是为了通过某一场考试更是为了在遇到资源调度、成本控制、投资组合等现实问题时能多一种强大而高效的思维方式。在平时的练习中不妨尝试一下它的变种比如“如果每个设备可以选多次完全背包怎么办”或者“要求输出具体选择了哪些设备”相信你会对动态规划有更深刻的体会。