洛谷P1489题解：动态规划解决分队问题
https://dajuwangluo.cn/zb_users/upload/2025/07/202507111752228593144223.jpg一、问题分析题目要求将n个人分成两队，使得两队总血量尽可能接近，同时两队人数也要尽可能平衡。这是一个典型的分组优化问题，可以使用动态规划高效解决。二、算法核心思路[*]动态规划定义：
[*]dp表示选i个人能否组成j血量
[*]采用三维降维优化，节省空间复杂度
[*]状态转移：
[*]逆序更新避免重复计算
[*]三重循环分别处理：人员、人数、血量
[*]最优解搜索：
[*]寻找最接近总血量一半的组合
[*]同时考虑人数平衡的优化
三、完整代码实现（带注释）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);// 加速输入输出
cin.tie(nullptr); // 解除cin与cout的绑定
int n;
cin >> n;
vector<int> blood(n);
int total = 0;
for (int i = 0; i < n; ++i) {
cin >> blood;
total += blood;
}
// dp表示选i个人能否组成j血量
vector<vector<bool>> dp(n/2+2, vector<bool>(total/2+1, false));
dp = true;// 初始状态：0个人0血量
for (int k = 0; k < n; ++k) {
for (int i = min(k, n/2); i >= 0; --i) {
for (int j = total/2; j >= blood; --j) {
if (dp]) {
dp = true;
}
}
}
}
// 寻找最优解：最接近total/2且人数最平衡
int best_sum = 0, best_count = 0;
for (int j = total/2; j >= 0; --j) {
for (int i = 0; i <= n/2; ++i) {
if (dp) {
if (abs(total-2*j) < abs(total-2*best_sum)) {
best_sum = j;
best_count = i;
} else if (abs(total-2*j) == abs(total-2*best_sum)) {
if (abs(n-2*i) < abs(n-2*best_count)) {
best_count = i;
}
}
}
}
}
cout << min(best_sum, total-best_sum) << " "
<< max(best_sum, total-best_sum) << endl;
return 0;
}
四、调试技巧
[*]使用小规模测试数据验证
[*]打印中间状态检查
[*]验证边界条件
[*]检查状态转移是否正确
参考：洛谷P1489题解：动态规划解决分队问题
页:
[1]