分成sum接近的2个集合,返回相对小的sum

题目描述：给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近，返回最接近的情况下，较小集合的累加和sum。

way：选还是不选

//arr[index...]可以自由选择,返回累加和尽量接近rest,但不能超过rest的情况下,最接近的值

#include<iostream>
#include<vector>
using namespace std;//arr[index...]可以自由选择,返回累加和尽量接近rest,但不能超过rest的情况下,最接近的值
int process(vector<int>arr, int index, int rest)
{//没有数可选if(index==arr.size()){return 0;}//如果不选当前数int p1=process(arr,index+1,rest);//如果选当前数（前提是可以选)int p2=0;if(rest-arr[index]>=0){p2=arr[index] + process(arr,index+1,rest-arr[index]);}return max(p1,p2);
}int way(vector<int>arr)
{//不合法的数组if(arr.size()<2) return -1;int sum=0,N=arr.size();for(int i=0; i<N; i++){sum+=arr[i];}return process(arr,0, sum>>1);
}

way2：dp版。

int dpWay(vector<int>arr)
{//不合法的数组if(arr.size()<2) return -1;int sum=0,N=arr.size();for(int i=0; i<N; i++){sum+=arr[i];}int half=(sum>>1);vector<vector<int>>dp(N+1, vector<int>(half+1));for(int index=N-1; index>=0; index--){for(int rest=0; rest<=half; rest++){int p1=dp[index+1][rest];int p2=0;if(rest-arr[index]>=0){p2=arr[index]+dp[index+1][rest-arr[index]];}dp[index][rest]=max(p1,p2);}}return dp[0][half];
}