找回密码
 立即注册
查看: 17|回复: 0

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

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:17
  • 打卡月天数:1
  • 打卡总奖励:185
  • 最近打卡:2025-08-06 09:29:10

21

主题

8

回帖

1万

积分

VIP

积分
10208
发表于 2025-7-28 14:54:38 | 显示全部楼层 |阅读模式
截图未命名.jpg
一、题目解读
洛谷P1489题要求将n个人的血量分配为两组,使两组血量之差最小,同时人数尽可能平衡。这是一类典型的组合优化问题,需要高效算法找到**解。题目难点在于如何在有限时间内计算所有可能的组合,并从中筛选出**结果。
二、解题思路
采用动态规划(Dynamic Programming)解决该问题。核心思想是将原问题分解为子问题,利用子问题的**解推导整体**解。通过构建二维dp数组dp[j]表示“选i个人能否组成j血量”,逐步迭代求解,最终找到最接近总血量一半的分配方案,并兼顾人数平衡。
三、解题步骤
1. 数据预处理:输入n和每个人的血量,计算总血量total,初始化dp数组。
2. 动态规划迭代:外层循环遍历人数k,内层双循环倒序枚举人数i和血量j,利用状态转移方程dp[i+1][j] = dp[j-blood[k]]更新。
3. **解筛选:从dp数组中寻找最接近total/2的血量值,同时比较人数差,优先选择人数更平衡的方案。
4. 输出结果:输出两组血量的最小值和**值。
四、代码与注释
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;

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

  8.     int n;
  9.     cin >> n;
  10.     vector<int> blood(n);
  11.     int total = 0;
  12.    
  13.     for (int i = 0; i < n; ++i) {
  14.         cin >> blood[i];
  15.         total += blood[i];
  16.     }

  17.     // dp[i][j]表示选i个人能否组成j血量
  18.     vector<vector<bool>> dp(n/2+2, vector<bool>(total/2+1, false));
  19.     dp[0][0] = true; // 初始状态:不选人时血量为0

  20.     for (int k = 0; k < n; ++k) {
  21.         for (int i = min(k, n/2); i >= 0; --i) {
  22.             for (int j = total/2; j >= blood[k]; --j) {
  23.                 if (dp[i][j-blood[k]]) { // 若存在前状态,更新当前状态
  24.                     dp[i+1][j] = true;
  25.                 }
  26.             }
  27.         }
  28.     }

  29.     // 寻找**解:最接近total/2且人数最平衡
  30.     int best_sum = 0, best_count = 0;
  31.     for (int j = total/2; j >= 0; --j) {
  32.         for (int i = 0; i <= n/2; ++i) {
  33.             if (dp[i][j]) {
  34.                 if (abs(total-2*j) < abs(total-2*best_sum)) {
  35.                     best_sum = j;
  36.                     best_count = i;
  37.                 } else if (abs(total-2*j) == abs(total-2*best_sum)) {
  38.                     if (abs(n-2*i) < abs(n-2*best_count)) {
  39.                         best_count = i;
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.     }

  45.     cout << min(best_sum, total-best_sum) << " "
  46.          << max(best_sum, total-best_sum) << endl;
  47.     return 0;
  48. }
复制代码


五、总结
本文通过动态规划方法解决了洛谷P1489的血量分配问题,核心在于将复杂组合问题转化为状态转移方程,并通过优化迭代过程降低时间复杂度。代码中通过倒序循环避免重复计算,**解筛选兼顾了血量差和人数平衡的双重要求,为同类背包问题提供了高效参考方案。
来源:洛谷题解

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

SEO网站 ( 冀ICP备2025113422号-2 )|网站地图

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表