【题目】
任意2N个正整数，从其中选出N个整数，使得选出的N个整数和同剩下的N个整数之和的差最小。
【来源】
网易
【分析】
假设数组A[1..2N]所有元素的和是SUM。模仿动态规划解0-1背包问题的策略。
从2N个数中找N个元素，有三种可能：大于Sum/2，小于Sum/2以及等于Sum/2。而大于Sum/2与小于等于Sum/2没区别，故可以只考虑小于等于Sum/2的情况。
令S(k, i)表示前k个元素中任意i个元素的和的集合。显然：
S(k, 1) = {A[i] | 1<= i <= k}
S(k, k) = {A[1]+A[2]+…+A[k]}
S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }
按照这个递推公式来计算，最后找出集合S(2N, N)中与SUM/2最接近的那个和，这便是答案。
【分析一】
状态转移方程：
其中，S[i-1][j][k]表示前i-1个元素中选取j个使其和不超过但最逼近k；
S[i-1][j-1][k-A[i]]在前i-1个元素中选取j-1个元素使其和不超过但最逼近k-A[i]，这样再加上A[i]即第i个元素就变成了 选择上第i个元素的情况下最逼近k的和。
而第一种情况与第二种情况是完备且互斥的，所以需要将两者最大的值作为F[i][j][k]的值。
可以设置一个三维数组Path[][][]来记录所选择元素的轨迹。根据求得的Path[][][]我们可以从S[2N][N][Sum/2]往S[0][0][0]逆着推导来打印轨迹对应的元素。
该算法的时间复杂度为O(n^2*sum)，空间复杂度也为O(n^2*sum)。
【代码一】
/*********************************
* 日期：2015-02-01
* 作者：SJF0115
* 题目: 数组分割
* 来源：网易
* 博客：
**********************************/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
// 模仿动态规划解0-1背包问题的策略
int MinSum(int num[],int n){
if(n <= 0){
return 0;
}//if
int sum = 0;
int size = 2*n;
// the sum of all number
for(int i = 1;i <= size;++i){
sum += num[i];
}//for
int dp[size + 1][n + 1][sum / 2 + 1];
// 选中数字路径
int path[size + 1][n + 1][sum / 2 + 1];
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
// 用dp(i,j,k)来表示从前i个元素中取j个元素,使得其和不超过k且最接近k,j <= min(i,n),k <= Sum/2
// 状态转移方程：
// dp(i,j,k)= max{dp(i-1,j-1,k-num[i])+num[i]，dp(i-1,j,k)}
// dp(2N,N,SUM/2+1)就是题目的解。
// 前i个元素
for(int i = 1;i <= size;++i){
// 任选j个元素
int count = min(i,n);
for(int j = 1;j <= count;++j){
// 使得其和不超过k且最接近k
for(int k = 1;k <= sum / 2;++k){
// dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-1][k-num[i]] + num[i]);
// 是否选第i个元素
dp[i][j][k] = dp[i-1][j][k];
if(k >= num[i] && dp[i-1][j][k] < dp[i-1][j-1][k-num[i]] + num[i]){
dp[i][j][k] = dp[i-1][j-1][k-num[i]] + num[i];
path[i][j][k] = 1;
}//if
}//for
}//for
}//for
// 打印选择路径
int i = 2*n,j = n,k = sum / 2;
while(i > 0 && j > 0, k > 0){
if(path[i][j][k] == 1){
cout<<num[i]<<" ";
--j;
k -= num[i];
}//if
--i;
}//while
cout<<endl;
int sum1 = dp[size][n][sum/2];
int sum2 = sum - dp[size][n][sum/2];
cout<<"Sum1->"<<sum1<<" sum2->"<<sum2<<endl;
return abs(sum1 - sum2);
}
int main(){
//int A[] = {0,1,5,7,8,9,6,3,11,20,17};
//int A[] = {0,1,2,3,4,5,6,7,8,9,10};
int A[] = {0,2,8,5,10};
int n = 2;
cout<<"最小差->"<<MinSum(A,n)<<endl;;
return 0;
}
【分析二】
我们从上面的代码可以看出，S[i][j][k]只与 S[i-1][][]有关，这一点状态方程上也能反映出来。这种固定关系我们可以想办法去掉。从而节省空间。
我们可以用二维数组来代替三维数组来达到降低空间复杂度的目的。
但是怎么代替呢？因为S[i][j][k]只与S[i-1][][]有关，可以把i这一维省略。
同时用二维数组来代替的时候应该对S[i][j][k]的“j”维进行逆序遍历。
为 什么? 因为只有这样才能保证计算S[i][j][k]时利用的S[i-1][j][]和S[i-1][j-1][]是真正i-1这个状态的值，如果正序遍 历，那么当计算S[][j][]时，S[][j-1][]已经变化，那么计算的结果就是错误的。
【代码二】
/*********************************
* 日期：2015-02-01
* 作者：SJF0115
* 题目: 数组分割
* 来源：网易
* 博客：
**********************************/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int MinSum(int num[],int n){
if(n <= 0){
return 0;
}//if
int sum = 0;
int size = 2*n;
// the sum of all number
for(int i = 1;i <= size;++i){
sum += num[i];
}//for
int dp[n + 1][sum / 2 + 1];
// 选中数字路径
int path[size+1][n + 1][sum / 2 + 1];
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
//
for(int i = 1;i <= size;++i){
// 任选j个元素
int count = min(i,n);
for(int j = count;j >= 1;--j){
// 使得其和不超过k且最接近k
for(int k = num[i-1];k <= sum / 2;++k){
if(dp[j][k] < dp[j-1][k-num[i-1]] + num[i-1]){
dp[j][k] = dp[j-1][k-num[i-1]] + num[i-1];
path[i][j][k] = 1;
}//if
}//for
}//for
}//for
// 打印选择路径
int i = 2 * n,j = n,k = sum / 2;
while(i > 0 && j > 0 && k > 0){
if(path[i][j][k] == 1){
cout<<num[i]<<" ";
--j;
k -= num[i];
}//if
--i;
}//while
cout<<endl;
int sum1 = dp[n][sum/2];
int sum2 = sum - dp[n][sum/2];
cout<<"Sum1->"<<sum1<<" sum2->"<<sum2<<endl;
return abs(sum1 - sum2);
}
int main(){
int A[] = {0,1,5,7,8,9,6,3,11,20,17};
//int A[] = {0,1,2,3,4,5,6,7,8,9,10};
//int A[] = {0,2,8,5,10};
int n = 5;
cout<<"最小差->"<<MinSum(A,n)<<endl;;
return 0;
}
【思路三】
/*-------------------------------------
* 日期：2015-02-01
* 作者：SJF0115
* 题目: 数组分割
* 来源：网易
* 博客：
------------------------------------*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int MinSum(int num[],int n){
if(n <= 0){
return 0;
}//if
int sum = 0;
int size = 2*n;
// the sum of all number
for(int i = 1;i <= size;++i){
sum += num[i];
}//for
// isOK[i][v]表示是否可以找到i个数，使得它们之和等于v
int isOK[n + 1][sum / 2 + 1];
int path[size + 1][n + 1][sum / 2 + 1];
// 都不合法
memset(isOK,0,sizeof(isOK));
memset(path,0,sizeof(path));
// 注意初始化
// 可以,取0件物品，总合为0，是合法的
isOK[0][0] = 1;
for(int i = 1;i <= size;++i){
int count = min(i,n);
for(int j = 1;j <= count;++j){
// 从大到小，数组少了一维
for(int k = sum / 2;k >= num[i];--k){
if( isOK[j-1][k-num[i]] ){
isOK[j][k] = 1;
path[i][j][k] = 1;
}//if
}//for
}//for
}//for
// 打印选择路径
int i = 2 * n,j = n,k = sum / 2;
while(i > 0 && j > 0 && k > 0){
if(path[i][j][k] == 1){
cout<<num[i]<<" ";
--j;
k -= num[i];
}//if
--i;
}//while
cout<<endl;
//
int minNum;
for(int k = sum / 2;k >= 0;--k){
if(isOK[n][k]){
minNum = k;
break;
}//if
}//for
int sum1 = minNum;
int sum2 = sum - minNum;
cout<<"Sum1->"<<sum1<<" sum2->"<<sum2<<endl;
return abs(sum1 - sum2);
}
int main(){
//int A[] = {0,1,5,7,8,9,6,3,11,20,17};
//int A[] = {0,1,2,3,4,5,6,7,8,9,10};
int A[] = {0,2,8,5,10};
int n = 2;
cout<<"最小差->"<<MinSum(A,n)<<endl;;
return 0;
}
