牛客网16949题：动态规划解决石头分组（01背包）问题

一、问题理解

给定一组石头，每个石头有不同的重量，我们需要将它们分成两组，使得两组的重量和尽可能接近。这是一个典型的优化问题，可以转化为背包问题来解决。

二、算法核心思想

1. ‌动态规划‌：使用0-1背包问题的变种来解决

2. ‌状态定义‌：dp[i]表示能否组成重量i

3. ‌状态转移‌：对于每个石头，更新可能达到的重量

三、关键步骤解析

1. ‌计算总重量‌：首先计算所有石头的总重量

2. ‌初始化DP数组‌：创建大小为总重量一半+1的布尔数组

3. ‌填充DP表‌：遍历每个石头，更新可能达到的重量

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;
    
    for (int stone : stones) {
        for (int i = half; i >= stone; --i) {
            if (dp[i - stone]) {
                dp[i] = true;
            }
        }
    }
    
    // 找到最接近half的可能重量
    int max_weight = 0;
    for (int i = half; i >= 0; --i) {
        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;
    
    // 读取输入，格式如：5,1,1,1,1,1
    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;
}

六、边界情况处理

1. ‌空输入‌：代码中已经处理了空输入情况

2. ‌单个石头‌：直接返回该石头的重量和0

3. ‌所有石头重量相同‌：可以完美分割的情况

来源：牛客题解