求两数组差的绝对值最小值
本帖最后由 sir_chen 于 2009-10-2 18:27 编辑有一个长度为n的数组a,暂不规定数组元素的类型,将这个数组划分成两个子数组,记这两个子数组的和分别为S1,S2,记两子数组和的差的绝对值ΔS=|S1-S2|.现在的问题是如何分组才能使ΔS最小.
我编了几个程序,但是时间复杂度都是O(2n),但是用lingo编程发现算的很快.不知道lingo是怎么实现的,感觉这道题有点类似0-1背包问题,但约束要少一些. 两个子数组的size确定不？ 实际上是将原数组进行一个分划,从原数组中选出若干个元素作为第一个子数组,剩下的就是第二个子数组的.两个子数组的元素个数不确定. 本帖最后由 sir_chen 于 2009-10-3 13:41 编辑
记两个子数组分别为A_0,A_1
记x_k={(0,(a_k in A_0)),(1,(a_k in A_1)):}
那么DeltaS=|sum_{k=1}^{n}x_k a_k-sum_{k=1}^{n}(1-x_k)a_k|=|2sum_{k=1}^{n}x_k a_k-S_n|
现在的任务是如何确定0-1变量x_k,使得DeltaS最小 这个是动态规划题.所有n个整数和为S,那么可以用O(S)的空间复杂度和O(n*S)的时间复杂度解决.
这个问题CSDN上经常讨论过 给出我的代码，效率比较低，采用动态规划做得
复杂度 O(sum * s1*s2)
原ACM题是将一数组化分为两数组， 使得他们和的差最小
同时两数组元素个数的差不超过1
#include <algorithm>
#include <numeric>
#include <bitset>
#include <vector>
using namespace std;
# define MAXN 100
# define MAXS 450
bitset<(MAXN + 1)*MAXS / 2> bs;
vector<int> vec;
// 4 1 2 4 10
int dp(int a[], int n)
{
std::sort(a + 1, a + n + 1);
if (n <= 2){
printf("%d %d\n", a, a);
return 0;
}
int sum = accumulate(a + 1, a + 1 + n, 0);
int minsum = a;
int maxlev = (n + 1) / 2;
bs.set(a);
vec.push_back(a);
for (int i = 2; i <= n; i++){
int curlev = min(i, maxlev); //update current curlev
for (int j = curlev - 1; j >= 0; j--){
for (int k = vec.size() - 1; k >= 0; k--){
int suma = vec + a;
if (suma <= sum / 2 && !bs.test(suma)){
if (j + 1 < maxlev){
bs.set(suma);
vec.push_back(suma);
}
if (suma > minsum){
if (j + 1 == maxlev && n % 2 == 0)
minsum = suma;
else if (j + 2 >= maxlev && n % 2 == 1)
minsum = suma;
if (minsum + 1 >= sum / 2)
break;
}
}
}
}
}
printf("%d %d\n", minsum, sum - minsum);
}
int main( )
{
int n;
int a = {0};
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
dp(a, n);
return 0;
}
页:
[1]