1. 项目概述与核心价值最近在准备华为OD机试的朋友尤其是目标C卷的同学应该都绕不开“挑选宝石”这道题。它不仅是2025年双机位C卷的真题更是一个考察你能否在有限时间内将数学思维转化为高效代码的绝佳案例。题目本身描述并不复杂给你一堆宝石每颗宝石有个价值你需要从中挑选若干颗使得它们的价值乘积大于等于一个目标值Y。听起来是不是有点像“子集”或者“组合”问题没错它的内核确实在此但直接套用回溯模板可能会让你在考场上超时。这道题真正的价值在于它用一个看似简单的场景逼着你思考如何在约束条件下进行算法优化以及如何写出健壮、清晰、符合C最佳实践的代码。对于正在刷题备战OD或者任何想提升自己解决组合优化问题能力的朋友来说吃透这道题收获的远不止一道题的解法。2. 题目深度解析与建模思路2.1 问题重述与输入输出规范我们先抛开代码把问题用人话再捋一遍。你有一个宝石集合假设大小为N。每颗宝石i有一个正整数值value[i]题目通常保证价值为正。同时你有一个目标阈值Y也是一个正整数。你的任务是找出所有不同的宝石组合也就是子集使得组合中所有宝石价值的乘积大于等于Y。你需要输出的是满足条件的所有不同组合的数量。这里有几个关键点需要立刻明确组合而非排列{宝石1 宝石2}和{宝石2 宝石1}被视为同一种组合这符合我们日常的认知。在算法上这通常意味着我们需要以一种“不回头”的顺序例如按索引递增来生成组合避免重复。乘积运算这是本题与经典子集和问题的核心区别。求和是线性的而乘积是指数增长的。一颗价值为10的宝石自己就能让乘积达到10两颗价值为10的宝石乘积就是100。这意味着数值的微小增长可能带来组合数量的剧变同时也提示我们当宝石价值较大时乘积很容易溢出整数范围这是编码时必须处理的坑。“大于等于”条件这是一个阈值判断不是精确匹配。这给剪枝优化提供了可能一旦当前累积乘积已经超过Y那么再乘以任何大于1的正整数结果只会更大依然满足条件。我们可以利用这一点提前终止某些搜索分支。输入格式通常会是两行第一行是宝石价值数组用空格分隔第二行是目标值Y。输出就是一个整数表示满足条件的组合数。2.2 核心挑战与算法选型分析看到“所有组合”很多人的第一反应是回溯法DFS。这确实是最直接的思路遍历所有可能的子集计算乘积并判断。对于N20的情况子集总数为2^N最多也就100万级别在现代计算机上暴力枚举是可行的。这也是很多题解给出的“保底”方案。但是如果N再大一些呢比如N302^30超过10亿暴力回溯就力不从心了。虽然本题明确N20但作为练习我们应当思考更优解。这就引出了第二个思路基于动态规划DP的计数。我们可以把问题转化为有多少个子集的乘积Y这有点像“背包问题”但背包问题是求和这里是求积。求积可以通过取对数转化为求和log(a*b) log(a) log(b)将乘法阈值Y转化为对数阈值log(Y)然后用一个DP数组dp[i][j]表示前i个宝石对数和对数值为j离散化后的组合数。然而由于浮点数精度问题和对数值的离散化处理这种方法实现起来较为复杂在机试的紧张环境中并非首选。对于机试场景在N较小20时采用回溯剪枝在N较大时考虑数学转化或DP是一个理性的判断。鉴于题目约束我们本篇将重点剖析回溯法的实现与极致优化这是面试官最可能期待的、清晰且高效的解法。注意机试时务必先确认数据范围如果题目描述或样例中暗示N很小回溯法就是最佳选择。如果N可能达到30甚至更大需要在思路阐述中提及对数DP的可能性以展示你思维的全面性。2.3 双机位考试环境下的编程要点“双机位”是华为OD线上考试的一种监考模式意味着对你的编程环境有更严格的限制。通常你会在一个定制的在线IDE如牛客网的系统中编码。这带来几个实际影响无法使用自定义头文件和复杂调试工具你几乎只能依赖标准库。因此代码必须简洁、自包含避免依赖平台特定的扩展。输入输出必须严格符合规范一般采用标准控制台输入输出cin/cout。要特别注意处理输入行的空格、换行输出格式必须精确匹配多一个空格都可能导致判题错误。时间与空间限制敏感虽然系统会给出限制但在回溯算法中递归深度最大等于N和中间状态存储需要留意。避免在递归函数中传递或返回大型容器如vector使用引用或全局变量来减少开销。代码风格与可读性清晰的代码结构、有意义的变量名、适当的注释即使在时间紧迫的情况下也能帮你减少错误并可能给阅卷人或自动评分系统留下好印象。3. 回溯法实现从暴力到优化3.1 基础回溯框架搭建我们从最朴素的深度优先搜索开始。核心思想是对于每一颗宝石我们有两种选择——“选它”或者“不选它”。我们递归地探索所有选择路径当探索完所有宝石时即到达递归树的叶子节点检查当前路径上已选宝石的乘积是否满足条件。#include iostream #include vector using namespace std; class Solution { private: int count 0; // 用于计数满足条件的组合 long long target; // 目标值Y用long long防止后续乘法溢出 vectorint gems; // 存储宝石价值 // 回溯函数 // index: 当前决策到第几颗宝石0-based // currentProduct: 当前已选宝石的乘积 void backtrack(int index, long long currentProduct) { // 递归终止条件已经考虑完所有宝石 if (index gems.size()) { if (currentProduct target) { count; } return; } // 选择1不选当前宝石 backtrack(index 1, currentProduct); // 选择2选当前宝石 // 注意如果当前乘积已经为0初始情况则乘以当前宝石价值否则直接乘。 long long newProduct (currentProduct 0) ? gems[index] : currentProduct * gems[index]; backtrack(index 1, newProduct); } public: int selectGems(vectorint values, int Y) { gems values; target Y; count 0; // 初始乘积设为0是一个特殊状态表示尚未选择任何宝石。 // 在递归中我们会正确处理它。 backtrack(0, 0); return count; } }; int main() { // 示例输入处理 vectorint values {2, 3, 4, 5}; int Y 20; Solution sol; int result sol.selectGems(values, Y); cout result endl; // 输出满足条件的组合数 return 0; }这就是回溯的骨架。backtrack函数像一棵二叉决策树在每个节点对应一颗宝石分叉。index控制我们遍历宝石的顺序确保每种组合只以一种顺序被生成例如总是按索引递增从而避免重复。3.2 关键优化乘积剪枝与去重上面的基础版本会探索所有2^N种可能效率低下。我们必须剪枝。优化一乘积剪枝可行性剪枝如果currentProduct已经大于等于target那么无论后续的宝石选还是不选最终乘积都一定大于等于target。对于当前路径剩下的remaining颗宝石从index到末尾每一种选择共2^remaining种都构成一个有效组合。我们可以直接计算这个数量而不用再递归下去。void backtrack(int index, long long currentProduct) { // 剪枝如果当前乘积已经达标 if (currentProduct target currentProduct ! 0) { // currentProduct为0是初始状态需排除 // 剩余宝石数量 gems.size() - index int remaining gems.size() - index; // 对于剩下的remaining颗宝石每颗都有选或不选两种可能共2^remaining种组合。 // 所有这些组合加上当前已选宝石都满足条件。 count (1 remaining); // 1 remaining 即 2^remaining return; // 无需继续递归 } if (index gems.size()) { // 这里不需要再判断因为如果走到叶子节点还没触发上面的剪枝说明currentProduct target // 因此这个组合不满足条件直接返回不用增加count。 return; } // 不选当前宝石 backtrack(index 1, currentProduct); // 选当前宝石只有当前乘积小于目标时才需要考虑选择否则在上一步已经剪枝了 // 同样需要处理初始乘积为0的情况 long long newProduct (currentProduct 0) ? gems[index] : currentProduct * gems[index]; // 这里可以加一个额外的剪枝如果newProduct因为溢出变成负数或0对于正数输入也可能需要处理但本题假设价值为正且用long long一般不会溢出。 backtrack(index 1, newProduct); }这个剪枝效果极其显著。一旦某条路径的累积乘积提前达标整棵子树都被跳过直接累加组合数。优化二排序与去重如果有重复宝石原题通常假设宝石价值可能相同但作为不同的个体。然而如果价值完全相同{宝石1 宝石2}和{宝石2 宝石1}在价值上是无法区分的但我们的回溯算法会因为索引不同而将其视为不同路径最终生成重复的组合。为了避免重复计数我们需要先对宝石价值进行排序然后在递归时对于连续相同价值的宝石进行“跳过”处理。但请注意“挑选宝石”题目的常规描述中每颗宝石是独立的即使价值相同也视为不同宝石。所以通常不需要去重。这里提出这一点是为了展示你思维的严密性。如果面试官追问“如果价值相同怎么处理”你可以给出排序后跳过相同元素的方案。在代码中如果不确定可以和面试官确认题意。3.3 处理大数溢出稳健的乘积计算这是本题一个非常容易踩坑的地方。宝石价值和目标值Y都是整数但乘积增长极快。例如10颗价值为10的宝石乘积就是10^10已经超过32位int的范围。即使使用long long通常64位最大值约9e18如果N稍大或价值稍大也极易溢出。溢出会导致负数或零使得剪枝逻辑和条件判断完全错误。解决方案提前终止与改用浮点数/对数边界检查在计算newProduct时检查是否会发生溢出。我们可以判断currentProduct LLONG_MAX / gems[index]。如果为真则说明乘法会溢出。此时因为currentProduct已经大于LLONG_MAX / gems[index]而gems[index] 1所以newProduct必定大于LLONG_MAX也就必定大于任何合理的target因为target也是一个有限整数。因此我们可以直接触发剪枝。#include climits // 用于LLONG_MAX ... long long newProduct; if (currentProduct 0) { newProduct gems[index]; } else { // 检查乘法是否溢出 if (currentProduct LLONG_MAX / gems[index]) { // 溢出意味着newProduct非常大肯定target (除非target也极大但题目范围通常不会) // 直接触发剪枝逻辑 int remaining gems.size() - index; // 注意当前宝石还未计入所以剩余是 size() - index count (1 remaining); return; // 不再继续递归“不选”的分支这里需要仔细思考。 // 实际上这里更安全的做法是既然选择当前宝石会导致溢出即乘积极大那么这条“选择”分支一定满足条件。 // 但“不选”分支还需要继续探索。所以不能直接return而应该处理完“不选”分支后对“选择”分支进行特殊处理。 // 一个更清晰的方法是在计算newProduct前判断如果会溢出则newProduct视为一个“无穷大”值在递归调用中触发剪枝。 } else { newProduct currentProduct * gems[index]; } }这段代码会变得有些复杂因为溢出检查打断了递归的流畅性。更优雅的方案使用double或long double。既然我们只需要比较乘积是否大于等于target而不需要精确的乘积值我们可以使用浮点数来计算乘积。double的范围非常大大约1e308足够应对绝大多数情况。同时我们还可以利用对数将乘法转换为加法彻底避免溢出并且能处理更大的数值。void backtrack(int index, double currentLogProduct) { // currentLogProduct 是已选宝石价值对数的和 if (currentLogProduct logTarget) { // logTarget log(Y) int remaining gems.size() - index; count (1 remaining); return; } if (index gems.size()) { return; } // 不选 backtrack(index 1, currentLogProduct); // 选 backtrack(index 1, currentLogProduct log(gems[index])); }这种方法非常巧妙将问题从“乘积阈值”转化为“对数和阈值”。需要注意的是浮点数存在精度误差在比较currentLogProduct logTarget时可能需要考虑一个微小的epsilon例如1e-12来避免因精度问题导致的误判。但在机试的整数价值场景下这个误差通常可以接受。实操建议在华为OD机试中如果明确给出了数值范围如价值10, N20使用long long并加上简单的溢出检查或干脆相信不会溢出是可行的。如果追求稳健使用double对数和方法是更优解它代码更简洁且能从根本上杜绝溢出担忧。我个人的选择是后者因为它一劳永逸。4. 完整代码实现与逐行解读综合以上优化我们给出一个使用double对数和的、带剪枝的完整回溯解法。这是我认为最适合机试场景的版本。#include iostream #include vector #include cmath // 用于log, exp #include algorithm // 用于sort如果想去重或优化剪枝顺序 using namespace std; class Solution { private: int count; double logTarget; // 目标值的自然对数 vectorint gems; vectordouble logValues; // 预计算好的每颗宝石价值的对数避免在递归中重复计算log void backtrack(int index, double currentLogSum) { // 剪枝当前对数之和已经达标 // 使用一个很小的epsilon来避免浮点数精度问题 if (currentLogSum - logTarget -1e-12) { int remaining gems.size() - index; count (1 remaining); return; } // 递归到底未达标 if (index gems.size()) { return; } // 分支1不选第index颗宝石 backtrack(index 1, currentLogSum); // 分支2选第index颗宝石 // 直接加上预计算好的对数值 backtrack(index 1, currentLogSum logValues[index]); } public: int selectGems(vectorint values, int Y) { gems values; int n gems.size(); count 0; logTarget log((double)Y); // 计算目标值的对数 // 预计算对数数组 logValues.resize(n); for (int i 0; i n; i) { // 题目保证宝石价值为正整数log参数为正 logValues[i] log((double)gems[i]); } // 可选优化对宝石按价值从大到小排序 // 这样在递归树中价值大的宝石先被考虑更容易早期触发乘积剪枝提升效率。 // 但注意排序会改变宝石顺序如果题目要求按原顺序或宝石有ID则不能简单排序。 // 这里假设我们只关心价值可以排序。 // 我们创建一个索引数组按价值降序排序然后按排序后的顺序进行回溯。 vectorint indices(n); for (int i 0; i n; i) indices[i] i; sort(indices.begin(), indices.end(), [](int a, int b) { return gems[a] gems[b]; // 降序排序 }); // 按照排序后的索引顺序重新安排宝石和对数值的顺序 vectorint sortedGems(n); vectordouble sortedLogValues(n); for (int i 0; i n; i) { sortedGems[i] gems[indices[i]]; sortedLogValues[i] logValues[indices[i]]; } gems sortedGems; logValues sortedLogValues; // 排序优化结束 // 开始回溯初始对数之和为0因为log(1)0未选任何宝石时乘积为1对数为0 // 但注意我们的剪枝条件是 currentLogSum logTarget。 // 如果初始就是0且logTarget是负数Y1时会直接触发剪枝这符合逻辑空集乘积为1若Y1则满足。 // 但题目通常Y1。我们按通用情况处理。 backtrack(0, 0.0); return count; } }; // 主函数处理输入输出 int main() { // 模拟机试的输入读取 vectorint values; int value; // 读取第一行宝石价值直到行尾 while (cin value) { values.push_back(value); if (cin.peek() \n) break; // 遇到换行符停止 } // 读取第二行目标值Y int Y; cin Y; Solution solution; int result solution.selectGems(values, Y); cout result endl; return 0; }代码解读与关键点对数转换logTarget log(Y)logValues[i] log(gems[i])。递归中传递的是对数和currentLogSum。判断条件currentLogSum logTarget等价于判断exp(currentLogSum) Y即乘积是否达标。预计算在递归前计算好所有logValues避免在递归栈中反复调用log()函数这是一个有效的性能优化。排序优化将宝石按价值降序排列。价值大的宝石先参与决策能更快地增大累积乘积对数和从而让“剪枝”条件更早被触发减少递归深度。这是一个非常实用的技巧。初始状态currentLogSum初始为0.0代表尚未选择任何宝石时的“乘积”为1因为log(1)0。这符合组合数学中空集的乘积定义为1的惯例。浮点数精度判断条件中使用了-1e-12作为容差epsilon。这是因为浮点数计算可能有微小误差例如理论上相等的两个数计算机表示可能差一点点。加上容差可以避免因精度问题漏掉本应有效的组合。这个值可以根据实际情况调整1e-12对于本题规模通常足够安全。输入处理主函数中的输入处理模拟了机试环境第一行连续读取整数直到换行第二行读取单个整数Y。这是一种健壮的读取方式。5. 测试用例与边界情况分析任何算法代码都必须经过充分测试。下面设计一组测试用例覆盖各种边界和典型场景。void test() { Solution sol; // 测试用例1基础功能 // 宝石: [2, 3, 4, 5], Y20 // 满足乘积20的组合有: [5,4]20, [5,4,2]40, [5,4,3]60, [5,4,3,2]120, [5,2,3]30, [4,5]20(重复)[5,4,2,3]120等。 // 需要仔细枚举。简单计算总组合2^416种。乘积小于20的有空集(1), [2]2, [3]3, [4]4, [5]5, [2,3]6, [2,4]8, [2,5]10, [3,4]12, [3,5]15, [2,3,4]24(20? 2420这个满足)等等。 // 手动枚举容易出错最好用一个小脚本验证。假设正确结果是8。 vectorint v1 {2, 3, 4, 5}; cout Test 1: sol.selectGems(v1, 20) (expected around 8, needs precise calculation) endl; // 测试用例2包含1的宝石 // 价值为1的宝石不影响乘积但会增加组合数量。 // 宝石: [1, 2, 3], Y4 // 满足条件的组合乘积4。 // [2,3]6, [1,2,3]6, [1,2]2(不满足), [1,3]3(不满足), [2]2(不满足), [3]3(不满足), [1]1(不满足), [1,2,3]和[2,3]都满足。 // 还有[1,2,3]和[2,3]已经算过。空集不满足。 // 所以只有2种等等[1,2]不满足[1,3]不满足。似乎只有包含2和3的组合才行。 // 包含2和3的组合有[2,3], [1,2,3]。所以是2种。 vectorint v2 {1, 2, 3}; cout Test 2: sol.selectGems(v2, 4) (expected 2) endl; // 测试用例3目标值Y1 // 任何非空集合的乘积都1因为价值是正整数空集乘积为1也满足。 // 所以所有子集都满足共2^N个。 vectorint v3 {1, 2, 3}; cout Test 3 (Y1): sol.selectGems(v3, 1) (expected 8) endl; // 测试用例4大数值导致乘积溢出验证对数法的稳健性 // 宝石: [1000000, 1000000, 1000000], Y10^18 // 三个10^6相乘是10^18刚好等于Y。所以组合有[A,B,C] (乘积10^18)满足。 // 还有包含[A,B], [A,C], [B,C]的乘积是10^12小于Y不满足。 // 单个宝石10^6也不满足。 // 所以只有1种组合满足。 vectorint v4 {1000000, 1000000, 1000000}; cout Test 4 (large values): sol.selectGems(v4, 1000000000000000000LL) (expected 1) endl; // 测试用例5空输入根据题意可能不会出现但测试鲁棒性 vectorint v5 {}; cout Test 5 (empty): sol.selectGems(v5, 5) (expected 0 or 1? 空集乘积为1若Y1则满足) endl; // 对于Y5空集乘积15所以应为0。 cout Test 5 (empty, Y1): sol.selectGems(v5, 1) (expected 1, only empty set) endl; // 测试用例6单个宝石 vectorint v6 {7}; cout Test 6 (single gem, Y5): sol.selectGems(v6, 5) (expected 1, because 75) endl; cout Test 6 (single gem, Y10): sol.selectGems(v6, 10) (expected 0) endl; }运行这些测试用例可以验证代码在常规情况、边界情况Y1空集大数下的正确性。对于测试用例1最好写一个简单的暴力枚举程序进行结果验证确保回溯剪枝的逻辑正确无误。6. 性能分析与替代方案探讨6.1 回溯法时间复杂度分析设宝石数量为N。最坏时间复杂度当所有宝石价值均为1且目标值Y1时任何子集的乘积都是1均小于Y剪枝几乎无效除了空集可能达标。算法会遍历所有2^N个子集时间复杂度为O(2^N)。最佳时间复杂度当第一颗宝石价值就大于等于Y时算法会在第一次递归选择该宝石时触发剪枝直接计算出2^(N-1)种组合并返回然后继续探索不选该宝石的分支。整体复杂度接近O(N)因为递归树很快被剪枝。平均情况依赖于数据分布。排序优化价值降序能极大提升平均性能因为它让大价值宝石优先参与决策提高了早期剪枝的概率。空间复杂度主要是递归调用栈的深度为O(N)。此外存储宝石价值和对数值的数组需要O(N)空间。对于N202^N ~ 1e6在现代CPU上完全可以在1秒内完成。这也是题目将N限制在较小范围内的原因使得回溯法成为可行解。6.2 动态规划DP方案思路对于更大的N例如N502^N是不可接受的。此时需要考虑DP。如前所述乘积问题可以通过取对数转化为求和问题。定义dp[i][j]为考虑前i个宝石对数值和恰好为j离散化后的子集数量。其中j的范围需要根据所有宝石对数值的总和来确定。目标是对所有j logTarget的dp[N][j]求和。步骤计算每颗宝石的对数值log_val[i] log(gems[i])。确定精度和范围将连续的对数值离散化。例如乘以一个大的缩放因子如1e6后取整转化为整数。初始化dp[0][0] 1空集对数和为0。状态转移对于第i颗宝石对数值lv离散化后为lv_intdp[i][j] dp[i-1][j] dp[i-1][j - lv_int]如果不选和选。最终答案sum(dp[N][j])for allj logTarget_int。这种方法的复杂度是O(N * M)其中M是离散化后对数值和的总范围。如果宝石价值范围不大M可以接受。但实现起来比回溯法复杂且要处理离散化精度问题。在机试中除非明确要求或N很大否则不建议优先采用但可以作为思路备选向面试官说明。6.3 位运算枚举迭代法由于N20我们也可以不用递归直接用位运算枚举所有子集。用一个从0到(1N)-1的整数mask的每一位来表示是否选择对应宝石。然后计算该mask对应子集的乘积或对数和判断是否达标。int count 0; int n gems.size(); double logTarget log(Y); vectordouble logGems(n); for(int i0; in; i) logGems[i] log(gems[i]); for(int mask 1; mask (1n); mask) { // 从1开始排除空集根据题目要求是否包含空集 double sumLog 0.0; for(int i0; in; i) { if(mask (1i)) { sumLog logGems[i]; // 可选的早期剪枝如果sumLog已经logTarget可以提前break内层循环 if(sumLog - logTarget -1e-12) { // 当前mask已经满足无需继续加其他宝石的对数 // 但注意即使提前break这个mask已经被计为有效。 // 我们可以在加完后再判断或者在这里设置一个标志。 break; } } } if(sumLog - logTarget -1e-12) { count; } } // 如果空集也满足条件(Y1)需要额外处理 if(Y 1) { count; // 加上空集 }这种方法代码更紧凑且没有递归开销。但缺点是无法像递归那样进行“子树剪枝”——我们无法在知道部分选择后直接推断出剩余所有组合是否有效。上面的“早期剪枝”只能跳过当前mask中剩余宝石的对数累加但不能跳过其他mask。因此在最坏情况下它仍然需要枚举所有2^N个mask每个mask可能遍历最多N个宝石总复杂度O(N * 2^N)比优化后的回溯法稍差。但对于N很小的情况两种方法都可以接受。7. 机试实战技巧与避坑指南结合华为OD机试的特点分享一些从这道题延伸出的通用实战技巧。仔细阅读题目描述和数据范围这是最重要的第一步。“N20”是选择回溯法的直接依据。还要注意宝石价值是否一定是正整数Y是否大于0结果是否需要对某个数取模等。这些细节决定你的初始化、边界处理和数据类型。选择合适的数据类型对于涉及乘积、幂运算的题目int往往不够用。优先使用long long。如果long long都可能溢出例如本题N20每个价值10乘积10^20就溢出了就要考虑double/long double或对数转换法。排序是廉价而有效的优化在允许改变顺序的情况下对输入数据进行排序升序或降序往往能帮助优化算法。例如本题降序排序让大数先参与计算加速剪枝。再比如在背包问题中按单位重量价值排序可以进行贪心选择虽然不是总得到最优解。剪枝要大胆且正确回溯法的核心优化就是剪枝。找到问题特有的剪枝条件如本题的乘积阈值并确保剪枝逻辑正确。特别是当剪枝后直接累加组合数时要仔细计算剩余的组合数2^remaining并确保当前状态本身已被计入。浮点数比较使用epsilon只要使用浮点数在比较相等或大小时就应使用一个极小的容忍度epsilon例如1e-9或1e-12。直接使用或可能会因精度问题导致错误结果。测试用例设计写完代码后不要只跑题目给的样例。自己设计边缘用例空数组、单个元素、全部元素相同、Y1、Y极大、数值极大导致溢出等。在机试环境中通常有自测功能要充分利用。代码风格与注释即使时间紧张也尽量让代码清晰。定义明确的变量名如currentLogSum比temp好在关键步骤如剪枝、溢出处理加一行简短注释。这不仅能帮助你自己调试也可能让阅卷人更容易理解你的思路。关于双机位环境在牛客或类似平台做题时注意输入输出格式。有些平台需要处理多组测试用例循环读取直到EOF。本题通常是一次性输入。使用while(cin value)读取一行数字是常用技巧。输出要严格符合要求不要输出额外的提示信息。回看“挑选宝石”这道题它完美地融合了基础的回溯思想、重要的剪枝优化、以及对数据溢出问题的警惕。掌握它不仅是为了通过某一场机试更是为了锻炼一种严谨的算法设计和实现能力。在实际的软件开发中这种将业务约束转化为高效、稳健代码的能力价值连城。
