题解 | #第二题#

题意理解：输入是一串字符串，将字符串转换成int数组，并划分出两个子数组num1,num2，使其和的差最小。

做题思路：设分为两个数组后，这两个数组元素和分别sum1，sum2。这里的差是指绝对值，也就是大的减去小的。在这里，我们先假设sum1≥sum2。那么要求的就是sum1-sum2的值最小。 设sum=sum1+sum2。可以知道，sum的大小是不变的，它就是未划分之前所有元素的和。 那么sum1-sum2=sum1+sum2-2sum2=sum-2sum2。这里就很明显了，因为sum是不变的，我们只要求出满足条件的最大的sum2。这里要注意到sum2满足sum1≥sum2这个条件。那么只用满足sum2≤sum/2即可。

题意转化为：从一个数组中选出若干数满足这些数的和最大 并且小于等于half。（其中half=sum/2，因为数组确定后sum就确定了，所以不妨假设这是一个常数）。

自然想到01背包问题，但是，01背包的体积V是有限制的，这里V可以很大：int范围内都可以取到，因此01背包问题不可用。

转而考虑DFS，但是这里输入又可能很大，所以考虑剪枝

首先需要判断输入是否合法（全是数字和空格），若不合法直接输出"ERROR"，进入下一次IO 若合法，将输入的字符串读入stringstream，用其来处理字符串->数字的转换,并将数字存入vector中。

计算数组总和sum，得到half，调用dfs函数

dfs搜索思路： val为当前搜索路径的权值，若val+num[i]<=half，则将当前数字加入搜索路径，进入深层搜索dfs(num,i+1,val+num[i]) 回溯后，选择不加入当前数字，再进入深层搜索,dfs(num,i+1,val)

剪枝条件： 若i>=num.size()则剪枝 若所有搜索路径中路径和最大值max_ans==half，则剪枝，已经找到了满足题意的最优解

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int sum,half,max_ans;//sum存储输入的数组的和,half存储数组和的一半，max_ans存储dfs中计算的最大满足条件的数组和

void dfs(vector<int> &num,int i,int val)
{
    max_ans=max(max_ans,val);//更新上一层的max_ans
    if(i>=num.size()) return;//超出搜索范围，剪枝

    if(max_ans==half) return;//满足条件，剪枝

    if(val+num[i]<=half)
        dfs(num,i+1,val+num[i]);//搜索路径1：加入当前节点

    dfs(num,i+1,val);//搜索路径2，不加入当前结点
}


void Solve(vector<int> &num)
{
    sum=half=max_ans=0;
    for(int i=0;i<num.size();i++)
        sum+=num[i];
    half=sum/2;//计算数组和的一半
    dfs(num,0,0);
    cout<<sum-max_ans<<" "<<max_ans<<endl;//小数在前，大数在后
}


int main()
{
    string line;
    while(getline(cin,line))
    {
        bool is_valid=true;//判断输入字符串是否只包括数字和空格
        for(int i=0;i<line.size();i++)
            if(!(line[i]>='0'&&line[i]<='9'||line[i]==' ')){
                is_valid=false;
                break;
            }

        if(!is_valid){
            printf("ERROR\n");
            continue;
        }

        stringstream ss;//stringstream用法
        ss<<line;//将字符串输入stringsream
        vector<int> num;
        int temp;
        while(ss>>temp) num.push_back(temp);//通过stringstream将字符串分割为数字
        Solve(num);

    }

    return 0;
}