洛谷P1489题解：动态规划解决分队问题

19339201706

一、问题分析

题目要求将n个人分成两队，使得两队总血量尽可能接近，同时两队人数也要尽可能平衡。这是一个典型的分组优化问题，可以使用动态规划高效解决。

二、算法核心思路

• 动态规划定义：
  
  
  • dp[j]表示选i个人能否组成j血量
  • 采用三维降维优化，节省空间复杂度
    
    
• 状态转移：
  
  
  • 逆序更新避免重复计算
  • 三重循环分别处理：人员、人数、血量
    
    
• 最优解搜索：
  
  
  • 寻找最接近总血量一半的组合
  • 同时考虑人数平衡的优化
    
    

三、完整代码实现（带注释）

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     ios::sync_with_stdio(false);  // 加速输入输出
   
8.     cin.tie(nullptr);             // 解除cin与cout的绑定
   
9.    
   
10.     int n;
    
11.     cin >> n;
    
12.     vector<int> blood(n);
    
13.     int total = 0;
    
14.    
    
15.     for (int i = 0; i < n; ++i) {
    
16.         cin >> blood[i];
    
17.         total += blood[i];
    
18.     }
    
19. 
    
20.     // dp[i][j]表示选i个人能否组成j血量
    
21.     vector<vector<bool>> dp(n/2+2, vector<bool>(total/2+1, false));
    
22.     dp[0][0] = true;  // 初始状态：0个人0血量
    
23. 
    
24.     for (int k = 0; k < n; ++k) {
    
25.         for (int i = min(k, n/2); i >= 0; --i) {
    
26.             for (int j = total/2; j >= blood[k]; --j) {
    
27.                 if (dp[i][j-blood[k]]) {
    
28.                     dp[i+1][j] = true;
    
29.                 }
    
30.             }
    
31.         }
    
32.     }
    
33. 
    
34.     // 寻找最优解：最接近total/2且人数最平衡
    
35.     int best_sum = 0, best_count = 0;
    
36.     for (int j = total/2; j >= 0; --j) {
    
37.         for (int i = 0; i <= n/2; ++i) {
    
38.             if (dp[i][j]) {
    
39.                 if (abs(total-2*j) < abs(total-2*best_sum)) {
    
40.                     best_sum = j;
    
41.                     best_count = i;
    
42.                 } else if (abs(total-2*j) == abs(total-2*best_sum)) {
    
43.                     if (abs(n-2*i) < abs(n-2*best_count)) {
    
44.                         best_count = i;
    
45.                     }
    
46.                 }
    
47.             }
    
48.         }
    
49.     }
    
50. 
    
51.     cout << min(best_sum, total-best_sum) << " "
    
52.          << max(best_sum, total-best_sum) << endl;
    
53.     return 0;
    
54. }

复制代码

四、调试技巧

• 使用小规模测试数据验证
• 打印中间状态检查
• 验证边界条件
• 检查状态转移是否正确
  
  

参考：洛谷P1489题解：动态规划解决分队问题