c++ - Codility MinAbsSum

Question

我试过这个 Codility 测试:MinAbsSum。 https://codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/

我通过搜索整个可能性树解决了这个问题。结果还可以，但是，由于大输入超时，我的解决方案失败了。换句话说，时间复杂度没有预期的那么好。我的解决方案是 O(nlogn)，这对树来说很正常。但是这个编码测试是在“动态编程”部分，并且必须有一些方法来改进它。我尝试先对整个集合求和，然后使用这些信息，但我的解决方案中总是缺少一些东西。有人知道如何使用 DP 改进我的解决方案吗？

#include <vector>
using namespace std;

int sum(vector<int>& A, size_t i, int s)
{
   if (i == A.size())     
      return s;

   int tmpl = s + A[i];
   int tmpr = s - A[i];
   return min (abs(sum(A, i+1, tmpl)), abs(sum(A, i+1, tmpr)));
}

int solution(vector<int> &A) {
   return sum(A, 0, 0);   
}

Answer 1

我解决不了。但是here's官方回答。

引用它:

Notice that the range of numbers is quite small (maximum 100). Hence,there must be a lot of duplicated numbers. Let count[i] denote thenumber of occurrences of the value i. We can process all occurrencesof the same value at once. First we calculate values count[i] Then wecreate array dp such that:

• dp[j] = −1 if we cannot get the sum j,
• dp[j] >= ­ 0 if we can get sum j.

Initially, dp[j] = -1 for all of j (except dp[0] = 0). Then we scanthrough all the values a appearing in A; we consider all a suchthat count[a]>0. For every such a we update dp that dp[j] denoteshow many values a remain (maximally) after achieving sum j. Notethat if the previous value at dp[j] >= 0 then we can set dp[j] =count[a] as no value a is needed to obtain the sum j. Otherwise wemust obtain sum j-a first and then use a number a to get sum j. Insuch a situation dp[j] = dp[j-a]-1. Using this algorithm, we canmark all the sum values and choose the best one (closest to half of S,the sum of abs of A).

def MinAbsSum(A):
    N = len(A)
    M = 0
    for i in range(N):
        A[i] = abs(A[i])
        M = max(A[i], M)
    S = sum(A)
    count = [0] * (M + 1)
    for i in range(N):
        count[A[i]] += 1
    dp = [-1] * (S + 1)
    dp[0] = 0
    for a in range(1, M + 1):
        if count[a] > 0:
            for j in range(S):
                if dp[j] >= 0:
                    dp[j] = count[a]
                elif (j >= a and dp[j - a] > 0):
                    dp[j] = dp[j - a] - 1
    result = S
    for i in range(S // 2 + 1):
        if dp[i] >= 0:
            result = min(result, S - 2 * i)
    return result

(请注意，由于最终迭代只考虑 S//2 + 1 之前的总和，我们可以通过只创建一个直到该值的 DP 缓存来节省一些空间和时间)

fladam 提供的 Java 答案返回输入 [2, 3, 2, 2, 3] 的错误结果，尽管它获得了 100% 的分数。

Java 解决方案

import java.util.Arrays;

public class MinAbsSum{
    static int[] dp;

    public static void main(String args[]) {
        int[] array = {1, 5,  2, -2};

        System.out.println(findMinAbsSum(array));
    }
    
    public static int findMinAbsSum(int[] A) {
        int arrayLength = A.length;
        int M = 0;
        for (int i = 0; i < arrayLength; i++) {
            A[i] = Math.abs(A[i]);
            M = Math.max(A[i], M);
        }
        
        int S = sum(A);
        dp = new int[S + 1];
        int[] count = new int[M + 1];
        for (int i = 0; i < arrayLength; i++) {
            count[A[i]] += 1;
        }
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i < M + 1; i++) {
            if (count[i] > 0) {
                for(int j = 0; j < S; j++) {
                    if (dp[j] >= 0) {
                        dp[j] = count[i];
                    } else if (j >= i && dp[j - i] > 0) {
                        dp[j] = dp[j - i] - 1;
                    }
                }
            }
        }
        int result = S;
        for (int i = 0; i < Math.floor(S / 2) + 1; i++) {
            if (dp[i] >= 0) {
                result = Math.min(result, S - 2 * i);
            }
        }
        return result;
    }

    public static int sum(int[] array) {
        int sum = 0;
        for(int i : array) {
            sum += i;
        }

        return sum;
    }
}