当前位置：首页 > news >正文

用C++暴力枚举解决厦大GPA最优分配问题（附完整代码）

news 2026/5/8 12:47:26

用C++暴力枚举解决GPA最优分配问题的工程实践

最近在算法竞赛社区看到一个有趣的题目：如何用编程方法求解四门考试总分下的最大GPA和。这个问题看似简单，但蕴含着许多值得探讨的算法思想和工程实践技巧。作为一名参加过多次算法竞赛的老手，我想分享一些关于这个问题的深入思考和解法优化。

1. 问题建模与暴力枚举基础

GPA计算问题本质上是一个离散优化问题。我们需要在四门课程的分数组合中，找到满足总分约束条件下GPA和最大的分配方案。厦门大学的GPA转换规则将百分制分数划分为11个区间，每个区间对应固定的绩点值。

最直观的解法就是暴力枚举所有可能的分数组合。由于每门课程只有11种可能的分数档位（对应绩点转换表中的边界值），四门课程的总组合数为11^4=14641种。在现代计算机的处理能力下，这个量级的枚举是完全可行的。

// 绩点转换表边界值 int scoreLevels[] = {90, 85, 81, 78, 75, 72, 68, 64, 60, 0};

暴力枚举的核心思路是预计算所有可能的分数组合及其对应的GPA和，然后建立GPA到最小总分的映射关系。这样对于任何给定的总分n，我们都能快速查找到不超过n的最大GPA和。

2. 预计算表的优化设计

原始代码中使用四重循环生成所有组合，这在算法正确性上没有问题，但从工程实践角度有几个可以优化的点：

数据结构选择：使用map存储GPA到最小总分的映射，并自定义比较器实现降序排列，这是合理的选择。但需要注意map的插入和查找操作都是O(log n)复杂度。
去重策略：当遇到相同GPA值时，只保留需要总分更小的记录。这个优化减少了不必要的存储，也加速了后续查询。

if(it == m.end()) { m.insert(make_pair(gpa, total)); } else { if(it->second > total) it->second = total; }

边界处理：总分n的范围是0到400，需要考虑所有边界情况。特别是当n小于最低可能总分时，应返回0.0。

3. 算法复杂度分析与优化空间

让我们分析一下这个解法的复杂度：

预处理阶段：11^4=14641次循环，每次循环包含map查找和插入操作，总复杂度约为O(14641 * log 14641) ≈ 200,000次操作
查询阶段：map已按GPA降序排列，只需线性扫描找到第一个满足条件的GPA值，平均复杂度O(1)

虽然这个复杂度对于题目约束已经足够，但我们还可以考虑以下优化方向：

剪枝策略：在四重循环中，如果当前部分分数和已经超过400，可以提前终止内层循环
并行计算：预处理阶段可以分块并行处理，利用多核CPU加速
记忆化搜索：改为递归实现并添加记忆化，可能减少部分重复计算

4. 工程实践中的注意事项

在实际编码实现时，有几个细节需要特别注意：

浮点数精度：GPA计算涉及浮点数，比较时应考虑精度问题。题目要求输出保留一位小数，可以使用iomanip中的fixed和setprecision控制输出格式。

cout << fixed << setprecision(1) << res << endl;

输入输出处理：题目没有说明有多少测试用例，代码中应使用while循环持续读取输入直到EOF。
代码可读性：将核心逻辑封装成函数（如getGPA、make_table等），避免将所有代码都放在main函数中。
性能测试：虽然本题数据规模不大，但养成测试习惯很重要。可以生成边界值测试用例验证代码正确性。

5. 问题扩展与变种思考

这个GPA优化问题可以衍生出许多有趣的变种：

课程数量变化：如果不是4门课而是k门课，解法该如何调整？当k较大时，暴力枚举不再适用，需要考虑动态规划等更高效的算法。
不同权重：如果各门课程学分不同，GPA计算需要加权平均，问题会变得更加复杂。
连续分数：当前问题是离散分数，如果允许任意百分制分数，问题将转变为连续优化问题，可能需要数学分析方法。
多目标优化：除了最大化GPA，可能还需要考虑分数分配的均衡性等其他目标。

6. 完整实现代码解析

以下是经过优化和详细注释的完整实现代码，包含了前面讨论的各种工程实践考虑：

#include <iostream> #include <map> #include <algorithm> #include <iomanip> using namespace std; // 自定义比较器，使map按GPA降序排列 class GPAComparator { public: bool operator()(float gpa1, float gpa2) const { return gpa1 > gpa2; } }; // 分数到GPA的转换函数 float scoreToGPA(int score) { if (score >= 90) return 4.0f; else if (score >= 85) return 3.7f; else if (score >= 81) return 3.3f; else if (score >= 78) return 3.0f; else if (score >= 75) return 2.7f; else if (score >= 72) return 2.3f; else if (score >= 68) return 2.0f; else if (score >= 64) return 1.7f; else if (score >= 60) return 1.0f; else return 0.0f; } // 预定义的分数档位 const int SCORE_LEVELS[] = {90, 85, 81, 78, 75, 72, 68, 64, 60, 0}; const int LEVEL_COUNT = 10; // 分数档位数量 map<float, int, GPAComparator> gpaToMinTotal; // GPA到最小总分的映射 // 预计算所有可能的分数组合 void buildGPATable() { for(int i = 0; i < LEVEL_COUNT; i++) { for(int j = 0; j < LEVEL_COUNT; j++) { for(int k = 0; k < LEVEL_COUNT; k++) { for(int d = 0; d < LEVEL_COUNT; d++) { int total = SCORE_LEVELS[i] + SCORE_LEVELS[j] + SCORE_LEVELS[k] + SCORE_LEVELS[d]; float gpa = scoreToGPA(SCORE_LEVELS[i]) + scoreToGPA(SCORE_LEVELS[j]) + scoreToGPA(SCORE_LEVELS[k]) + scoreToGPA(SCORE_LEVELS[d]); // 更新GPA到最小总分的映射 auto it = gpaToMinTotal.find(gpa); if(it == gpaToMinTotal.end()) { gpaToMinTotal[gpa] = total; } else if(total < it->second) { it->second = total; } } } } } } // 查询给定总分下的最大GPA和 float queryMaxGPA(int totalScore) { for(const auto& entry : gpaToMinTotal) { if(entry.second <= totalScore) { return entry.first; } } return 0.0f; } int main() { // 预计算GPA表 buildGPATable(); int totalScore; while(cin >> totalScore) { float maxGPA = queryMaxGPA(totalScore); cout << fixed << setprecision(1) << maxGPA << endl; } return 0; }