求两数组差的绝对值最小值

sir_chen

有一个长度为n的数组a[n],暂不规定数组元素的类型,将这个数组划分成两个子数组,记这两个子数组的和分别为S₁,S₂,记两子数组和的差的绝对值ΔS=|S₁-S₂|.现在的问题是如何分组才能使ΔS最小. 我编了几个程序,但是时间复杂度都是O(2ⁿ),但是用lingo编程发现算的很快.不知道lingo是怎么实现的,感觉这道题有点类似0-1背包问题,但约束要少一些.

kon3155

两个子数组的size确定不？

sir_chen

实际上是将原数组进行一个分划,从原数组中选出若干个元素作为第一个子数组,剩下的就是第二个子数组的.两个子数组的元素个数不确定.

sir_chen

记两个子数组分别为$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$最小

mathe

这个是动态规划题.所有n个整数和为S,那么可以用O(S)的空间复杂度和O(n*S)的时间复杂度解决. 这个问题CSDN上经常讨论过

tprime

给出我的代码，效率比较低，采用动态规划做得 复杂度 O(sum * s1*s2) 原ACM题是将一数组化分为两数组， 使得他们和的差最小 同时两数组元素个数的差不超过1 #include #include #include #include using namespace std; # define MAXN 100 # define MAXS 450 bitset<(MAXN + 1)*MAXS / 2> bs[MAXN / 2 + 1]; vector vec[MAXN /2 + 1]; // 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[n - 1], a[n]); return 0; } int sum = accumulate(a + 1, a + 1 + n, 0); int minsum = a[1]; int maxlev = (n + 1) / 2; bs[1].set(a[1]); vec[1].push_back(a[1]); 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[j].size() - 1; k >= 0; k--){ int suma = vec[j][k] + a[i]; if (suma <= sum / 2 && !bs[j + 1].test(suma)){ if (j + 1 < maxlev){ bs[j + 1].set(suma); vec[j + 1].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[MAXN + 1] = {0}; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); dp(a, n); return 0; }