洛谷P1489题解析：动态规划求解血量分配问题的优化方案

一、题目解读

洛谷P1489题要求将n个人的血量分配为两组，使两组血量之差最小，同时人数尽可能平衡。这是一类典型的组合优化问题，需要高效算法找到最优解。题目难点在于如何在有限时间内计算所有可能的组合，并从中筛选出最优结果。

二、解题思路

采用动态规划（Dynamic Programming）解决该问题。核心思想是将原问题分解为子问题，利用子问题的最优解推导整体最优解。通过构建二维dp数组dp[i][j]表示“选i个人能否组成j血量”，逐步迭代求解，最终找到最接近总血量一半的分配方案，并兼顾人数平衡。

三、解题步骤

1. 数据预处理：输入n和每个人的血量，计算总血量total，初始化dp数组。

2. 动态规划迭代：外层循环遍历人数k，内层双循环倒序枚举人数i和血量j，利用状态转移方程dp[i+1][j] = dp[i][j-blood[k]]更新。

3. 最优解筛选：从dp数组中寻找最接近total/2的血量值，同时比较人数差，优先选择人数更平衡的方案。

4. 输出结果：输出两组血量的最小值和最大值。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加快输入输出速度

    int n;
    cin >> n;
    vector<int> blood(n);
    int total = 0;
    
    for (int i = 0; i < n; ++i) {
        cin >> blood[i];
        total += blood[i];
    }

    // dp[i][j]表示选i个人能否组成j血量
    vector<vector<bool>> dp(n/2+2, vector<bool>(total/2+1, false));
    dp[0][0] = true; // 初始状态：不选人时血量为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[k]; --j) {
                if (dp[i][j-blood[k]]) { // 若存在前状态，更新当前状态
                    dp[i+1][j] = 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[i][j]) {
                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的血量分配问题，核心在于将复杂组合问题转化为状态转移方程，并通过优化迭代过程降低时间复杂度。代码中通过倒序循环避免重复计算，最优解筛选兼顾了血量差和人数平衡的双重要求，为同类背包问题提供了高效参考方案。