牛客16949题：动态规划求解石头分组最小重量差问题
一、题目解读
牛客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;
}五、总结
本解法通过动态规划将问题转化为01背包变种，巧妙利用反向查找优化复杂度。核心在于理解“最小重量差”等价于“是否存在接近总重量一半的组合”，时间复杂度为O(n*sum)，空间为O(sum)。掌握此类DP模型对解决资源分配、分组优化问题有重要启发。
原创内容 转载请注明出处
