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

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 <algorithm>
#include <numeric>
#include <bitset>
#include <vector>
using namespace std;

# define MAXN 100
# define MAXS 450

bitset<(MAXN + 1)*MAXS / 2> bs[MAXN / 2 + 1];
vector<int> 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;
}