一、题目概述:有一个没有排序,元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组,并使两个子数组的和最接近。
假设数组A[1..2N]所有元素的和是SUM。模仿动态规划解0-1背包问题的策略,令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最接近的那个和,这便是答案。这个算法的时间复杂度是O(2^N).
因为这个过程中只关注和不大于SUM/2的那个子数组的和。所以集合中重复的和以及大于SUM/2的和都是没有意义的。把这些没有意义的和剔除掉,剩下的有意义的和的个数最多就是SUM/2个。所以,我们不需要记录S(2N,N)中都有哪些和,只需要从SUM/2到1遍历一次,逐个询问这个值是不是在S(2N,N)中出现,第一个出现的值就是答案。我们的程序不需要按照上述递推公式计算每个集合,只需要为每个集合设一个标志数组,标记SUM/2到1这个区间中的哪些值可以被计算出来。关键代码如下:
#include<iostream>
using namespace std;
//有一个没有排序,元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组,并使两个子数组的和最接近。
int arr[] = {0,1,5,7,8,9,6,3,11,20,17};
const int N=5;
const int SUM = 87;
// 模仿动态规划解0-1背包问题的策略
int solve1()
{
int i , j , s;
int dp[2*N+1][N+1][SUM/2+2];
/*
用dp(i,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案,在这里i>=j,c<=S
状态转移方程:
限第i个物品 不取
dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i],dp(i-1,j,c)}
dp(2N,N,SUM/2+1)就是题目的解。
*/
//初始化
memset(dp,0,sizeof(dp));
for(i = 1 ; i <= 2*N ; ++i)
{
for(j = 1 ; j <= min(i,N) ; ++j)
{
for(s = SUM/2+1 ; s >= arr[i] ; --s)
{
dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i] , dp[i-1][j][s]);
}
}
}
//因为这为最终答案 dp[2*N][N][SUM/2+1];
i=2*N , j=N , s=SUM/2+1;
while(i > 0)
{
if(dp[i][j][s] == dp[i-1][j-1][s-arr[i]]+arr[i]) //判定这个状态是由哪个状态推导出来的
{
cout<<arr[i]<<" "; //取中arr[i]
j--;
s -= arr[i];
}
i--;
}
cout<<endl;
return dp[2*N][N][SUM/2+1];
}
int solve2()
{
int i , j , s;
int dp[N+1][SUM/2+2]; //取N+1件物品,总合不超过SUM/2+2,的最大值是多少
memset(dp,0,sizeof(dp)); //初始状态都为0
for(i = 1 ; i <= 2*N ; ++i)
{
for(j = 1 ; j <= min(i,N) ; ++j)
{
for(s = SUM/2+1 ; s >= arr[i] ; --s) //01背包从大到小,可以省空间,即最外层的空间
{
dp[j][s] = max(dp[j-1][s-arr[i]]+arr[i] , dp[j][s]);
}
}
}
//要求最优解则 空间不能优化,
return dp[N][SUM/2+1];
}
int solve3()
{
int i , j , s;
int isOK[N+1][SUM/2+2]; //isOK[i][v]表示是否可以找到i个数,使得它们之和等于v
memset(isOK,0,sizeof(isOK)); //都不合法
//注意初始化
isOK[0][0] = 1; //可以,取0件物品,总合为0,是合法的
for(i = 1 ; i <= 2*N ; ++i)
{
for( j = 1 ; j <= min(i,N) ; ++j)
{
for(s = SUM/2+1 ; s >= arr[i] ; --s) //从大到小,数组少了一维
{
if( isOK[j-1][s-arr[i]] )
isOK[j][s] = 1;
}
}
}
for(s = SUM/2+1 ; s >= 0 ; --s)
{
if(isOK[N][s])
return s;
}
//要求最优解则空间不能优化
return 0;
}
int main(void)
{
int s1 = solve1();
int s2 = solve2();
int s3 = solve3();
cout<<"s1="<<s1<<endl;
cout<<"s2="<<s2<<endl;
cout<<"s3="<<s3<<endl;
system("pause");
return 0;
}
二、扩展问题: 交换两个数组元素使两个数组和的差最小
有两个数组a、b,大小都为n,数组元素的值任意整形数,无序;
要求:通过交换a、b数组中的元素,使[数组a元素的和]与[数组b元素的和]之间的差最小。
其实这个问题就是上面问题的变形,将a、b两个数组合并为一个数组,然后问题就转化为将2*n个元素数组分割为2个长度为n的数组,并使两个子数组的和最接近。
另外,特别注意:如果数组中有负数的话,上面的背包策略就不能使用了(因为第三重循环中的s是作为数组的下标的,不能出现负数的),需要将数组中的所有数组都加上最小的那个负数的绝对值,将数组中的元素全部都增加一定的范围,全部转化为正数,然后再使用上面的背包策略就可以解决了。
分享到:
相关推荐
ArrayList和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector...
答:1:确保每列都是不可分割的原子值 2:确保每列都和主键相关 3:确保每列都和主键直接相关,而不是间接相关 单例模式有哪些好处? 答:单例模式是一种比较常见的设计模式,带给我们以下好处: 1:控制资源的...
超级有影响力的Java面试题大全文档 1.抽象: 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节。...
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*...84. C语言惠通面试题 428 85. C语言常用宏定义 450
35、如何把一段逗号分割的字符串转换成一个数组? 24 36、数组有没有length()这个方法? String有没有length()这个方法? 24 37、下面这条语句一共创建了多少个对象:String s="a"+"b"+"c"+"d"; 24 38、try {}里有一个...
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
不多说了 直接上目录: 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450 有需要的朋友可以根据需求下载,内容为WORD格式的,绝对清晰
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
高级进阶c语言教程 目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
C语言编程准则之稳定篇 ............................................................................................................ 96 21. C语言编程常见问题分析 ..........................................