题解 | 分石头

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> splitStones(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        
        // dp[i]表示是否能得到重量i
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        
        // 01背包
        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        
        // 找到最接近target的重量
        int group1 = target;
        while (!dp[group1]) group1--;
        int group2 = sum - group1;
        
        return {max(group1, group2), min(group1, group2)};
    }
};

int main() {
    string input;
    getline(cin, input);
    
    // 解析输入
    vector<int> stones;
    stringstream ss(input);
    string num;
    while (getline(ss, num, ',')) {
        stones.push_back(stoi(num));
    }
    
    Solution sol;
    vector<int> result = sol.splitStones(stones);
    
    // 输出结果
    cout << result[0] << "," << result[1] << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int[] splitStones(int[] stones) {
            int sum = Arrays.stream(stones).sum();
            int target = sum / 2;
            
            // dp[i]表示是否能得到重量i
            boolean[] dp = new boolean[target + 1];
            dp[0] = true;
            
            // 01背包
            for (int stone : stones) {
                for (int j = target; j >= stone; j--) {
                    dp[j] |= dp[j - stone];
                }
            }
            
            // 找到最接近target的重量
            int group1 = target;
            while (!dp[group1]) group1--;
            int group2 = sum - group1;
            
            return new int[]{Math.max(group1, group2), Math.min(group1, group2)};
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(",");
        
        int[] stones = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            stones[i] = Integer.parseInt(input[i]);
        }
        
        Solution sol = new Solution();
        int[] result = sol.splitStones(stones);
        
        System.out.println(result[0] + "," + result[1]);
        sc.close();
    }
}

class Solution:
    def split_stones(self, stones: list) -> list:
        total = sum(stones)
        target = total // 2
        
        # dp[i]表示是否能得到重量i
        dp = [False] * (target + 1)
        dp[0] = True
        
        # 01背包
        for stone in stones:
            for j in range(target, stone - 1, -1):
                dp[j] |= dp[j - stone]
        
        # 找到最接近target的重量
        group1 = target
        while not dp[group1]:
            group1 -= 1
        group2 = total - group1
        
        return [max(group1, group2), min(group1, group2)]

def main():
    stones = list(map(int, input().split(',')))
    
    sol = Solution()
    result = sol.split_stones(stones)
    
    print(f"{result[0]},{result[1]}")

if __name__ == "__main__":
    main()