当前位置：首页 > 牛客 > 牛客16949题：动态规划求解石头分组最小重量差问题

牛客16949题：动态规划求解石头分组最小重量差问题

8个月前 (08-19)

一、题目解读

牛客16949题要求将一组石头分成两部分，使两组的重量差最小。题目给出一个整数数组stones，每个元素代表一块石头的重量，需找到一种分组方案，使得两组总重量之差绝对值最小。例如，当输入[5,1,1,1,1,1]时，最优分组为[5]和[1,1,1,1,1]，重量差为0。

二、解题思路

采用动态规划（DP）解决该问题，核心思想是将问题转化为“能否用部分石头组成目标重量”。具体策略如下：

1. 总重量计算：先求所有石头总重量total，目标为找到最接近total/2的重量组合。

2. 动态规划：定义布尔型DP数组dp[i]表示是否存在一种方案使石头组合重量为i。

3. 状态转移：从大到小遍历每个石头重量stone，若dp[i-stone]为真，则更新dp[i]为真（即当前石头可加入已有组合）。

4. 寻找最优解：反向遍历dp数组，找到第一个满足dp[i]且i接近total/2的值，该值即为最大可组合重量，剩余重量即为另一组重量。

三、解题步骤

1. 初始化：

计算总重量total并取半（half = total / 2）。

创建DP数组dp[0..half]，初始化dp[0]=true（空组合重量为0）。

2. 填充DP数组：

外层循环遍历每个石头stone。

内层倒序循环i=half..stone，若dp[i-stone]为真，则更新dp[i]为真（表示可组合）。

3. 寻找最接近目标重量：

反向遍历dp数组，找到第一个dp[i]为真的i，记为max_weight。

另一组重量为total - max_weight。

4. 返回结果：取两组重量中较大和较小的值，形成答案数组。

四、代码与注释

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

// 核心函数：计算石头分组的最小重量差
vector<int> partitionStones(vector<int>& stones) {
    int total = accumulate(stones.begin(), stones.end(), 0);  // 总重量
    int half = total / 2;                                  // 目标半重量
    int n = stones.size();
    
    // dp[i]：是否存在组合重量为i
    vector<bool> dp(half + 1, false);
    dp[0] = true;                                          // 空组合重量为0，默认成立
    
    // 动态规划填充
    for (int stone : stones) {                            // 遍历每块石头
        for (int i = half; i >= stone; --i) {             // 倒序遍历可能的重量
            if (dp[i - stone]) {                         // 若可减去该石头形成i
                dp[i] = true;                            // 更新状态
            }
        }
    }
    
    // 寻找最接近half的可组合重量
    int max_weight = 0;
    for (int i = half; i >= 0; --i) {                     // 反向查找第一个true
        if (dp[i]) {
            max_weight = i;
            break;
        }
    }
    
    int other = total - max_weight;                       // 另一组重量
    return {max(other, max_weight), min(other, max_weight)};  // 返回较大和较小重量
}

int main() {
    vector<int> stones;
    int num;
    char comma;
    
    // 输入处理：逗号分隔的石头重量
    while (cin >> num) {
        stones.push_back(num);
        if (cin.peek() == ',') {                          // 检查逗号分隔符
            cin >> comma;
        } else {
            break;
        }
    }
    
    vector<int> result = partitionStones(stones);
    cout << result[0] << "," << result[1] << endl;         // 输出结果
    return 0;
}