《算法笔记》11.8小节——动态规划专题-＞总结 问题 A: 第二题
题目描述
一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组各元素之和a,b的差最小，对于非法输入应该输出ERROR。
输入
数组中的元素
输出
降序输出两个子数组的元素和
样例输入
10 20 30 10 10
10 20 abc 10 10样例输出
40 40
ERROR分析：这道题虽然没给数据范围，但是根据提交后的结果，大概可以判断由于给出的元素和数量级在 10 的 8 次方左右，数据过大，无法使用动态规划的方法解决。可以使用折半枚举的方法来完成这道题。
将原数组拆成两半，枚举前半部分的所有子集和，存入数组并排序；枚举后半部分所有子集和，然后在前半数组的子集和中用二分搜索，找到最接近总和一半的组合。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);clock_t start=clock();#endif //testchar s[1000];while(fgets(s,1000,stdin)){int len=strlen(s),t=0,f=1,sum=0;vector<int>num;for(int i=0;i<len;++i){int index;for(index=i;index<len;++index){if(s[index]==' '||s[index]=='\n')break;else if(!isdigit(s[index])){f=0;break;}}if(!f)break;int temp=0;for(int j=i;j<index;++j){temp=temp*10+s[j]-'0';}
// db1(temp);i=index;sum+=temp;num.push_back(temp);}if(!f){printf("ERROR\n");continue;}int n=num.size(),n1=n-n/2,n2=n-n1,ret=sum,m1=1<<n1,m2=1<<n2;int cnt[1<<15]={0};for(int i=0;i<m1;++i){int j,k;for(j=k=0;j<n1;++j)if(i&(1<<j))k+=num[j];cnt[i]=k;}sort(cnt,cnt+m1);int l=0,r=m1;for(int i=0;i<m2;++i){int j,k;for(j=k=0;j<n2;++j)if(i&(1<<j))k+=num[n1+j];l=0,r=m1;while(l<r){int temp=k+cnt[(l+r)/2];if(temp<sum-temp)l=(l+r)/2+1;else r=(l+r)/2;}if(l<m1&&k+cnt[l]-(sum-k-cnt[l])<ret)ret=k+cnt[l]-(sum-k-cnt[l]);if(l>0&&sum-k-cnt[l-1]-k-cnt[l-1]<ret)ret=sum-k-cnt[l-1]-k-cnt[l-1];}printf("%d %d\n",(sum+ret)/2,(sum-ret)/2);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}