For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|

(Assume that the sum of zero elements equals zero.)

For a given array A, we are looking for such a sequence S that minimizes val(A,S).

Write a function:

int solution(int A[], int N);

that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.

For example, given array:

A[0] = 1 A[1] = 5 A[2] = 2 A[3] = -2

your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.

Assume that:

• N is an integer within the range [0..20,000];
• each element of array A is an integer within the range [−100..100].

Complexity:

• expected worst-case time complexity is O(N*max(abs(A))2);
• expected worst-case space complexity is O(N+sum(abs(A))), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

题目大意：给n个数，每个数的范围在-100到100之间，然后对于每个数，我们可以选着乘上-1或1，然后让你求出这些数的和的绝对值的最小值。

这题，可以转化成背包问题。

很明显，我们对这些数求和得sum ，用多重背包求得接近<=sum/2的最大值ans,那么sum-ans-ans就是结果了....这里不好语言描述，不过想一想还是很正确的.

把多重背包转换成01背包求。时间复杂度：O(V*Σlog n[i])  这里的V=sum/2

// you can use includes, for example:// #include <algorithm>// you can write to stdout for debugging purposes, e.g.// cout << "this is a debug message" << endl;int dp[1000010];int V;inline void dp1(int cost,int weight){    for(int v=V;v>=cost;v--)        dp[v]=max(dp[v],dp[v-cost]+weight);}inline void dp2(int cost,int weight){    for(int v=cost;v<=V;v++){        dp[v]=max(dp[v],dp[v-cost]+weight);    }}inline void dp3(int cost,int weight,int num){    if(cost*num>=V){        dp2(cost,weight);        return ;    }    int  k=1;    while(k<num){        dp1(k*cost,k*weight);        num-=k;        k*=2;    }    dp1(num*cost,num*weight);}int cnt[102];int solution(vector<int> &A) {    // write your code in C++11 (g++ 4.8.2)    int n=A.size();    int sum,m;    sum=m=0;    dp[0]=0;    for(int i=0;i<n;i++){        int x=(A[i]>=0)?A[i]:(-A[i]);        sum+=x;        cnt[x]++;        if(x>m)m=x;    }    if(m==0)return 0;    V=(sum>>1);    for(int i=1;i<=m;i++){        if(cnt[i])dp3(i,i,cnt[i]);    }    return (sum-(dp[V]<<1));    }

 more about 多重背包：http://love-oriented.com/pack/P03.html

codility MinAbsSum