编程之美-数组分割
编程之美'数组分割'和扩展
将一个数组划分成两个子数组，要求他们的和最接近1.长度要求相等的情况： 2.长度没有要求的情况：
都能用动态规划解决

#include<iostream>#include<algorithm>using namespace std;void ArraySplit1(int a[], int n)//两个子数组长度要求相等{int dp[20][20][200]; //k:当前元素   i:元素个数  j:元素和int sum=0;for(int k=0; k<n; k++)sum += a[k];cout<<"sum: "<<sum<<endl; for(int k=0; k<=n; k++) dp[k][0][0] = 0;for(int k=1; k<=n; k++)for(int i=0; i<=min(k,n/2); i++)for(int j=0; j<=sum/2; j++) //{if(a[k-1]<=j && dp[k-1][i-1][j-a[k-1]] >= 0)dp[k][i][j] = k;  else if(k>i)dp[k][i][j] = dp[k-1][i][j];elsedp[k][i][j] = -1;  }int k=n;int i=n/2;int j=sum/2;while(dp[k][i][j] <0 )j--;int part = 0;while(i>0){if(dp[k][i][j] == k){cout<<a[k-1]<<" ";part += a[k-1];j -= a[k-1];k--;i--;}else if(dp[k][i][j] > 0){--k;}}cout<<endl;cout<<"part: "<<part<<endl;       }void ArraySplit2(int a[], int n) //两个子数组长度不要求相等{int dp[20][200];int sum=0;for(int k=1; k<=n; k++){sum += a[k-1];dp[k][0] = 0;dp[0][k] = -1;}dp[0][0] = 0;cout<<"sum: "<<sum<<endl;for(int k=1; k<=n; k++){for(int j=1; j<=sum/2; j++){if(j>=a[k-1] && dp[k-1][j-a[k-1]]>=0)dp[k][j] = k;elsedp[k][j] = dp[k-1][j];}}int j=sum/2;int k=n;while(dp[k][j] < 0)j--;int part=0;while(k>0){if(dp[k][j] == k){cout<<a[k-1]<<" ";part += a[k-1];j -= a[k-1];k--;}else{k--;}}cout<<endl;cout<<"part: "<<part<<endl;}int main(){int a[] = {1,5,7,8,9,6,3,15,21,18,30,23};ArraySplit1(a,12); ArraySplit2(a,12); getchar();return 0;}