Codility Lesson 17 - Dynamic programming

MinAbsSum

Ambitious
Given array of integers, find the lowest absolute sum of elements.

 

app.codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/

MinAbsSum coding task - Learn to Code - Codility

N 개의 정수로 구성된 배열 A와 {-1, 1} 집합에서 N 개의 정수로 구성된 시퀀스 S에 대해 다음과 같이 val (A, S)를 정의합니다.

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

(0 개 요소의 합이 0이라고 가정합니다.)

주어진 배열 A에 대해 우리는 val (A, S)를 최소화하는 시퀀스 S를 찾고 있습니다.

함수 작성 :

class Solution {public int solution (int [] A); }

N 개의 정수 배열 A가 주어지면 {-1, 1} 집합에서 N 개 정수의 가능한 모든 시퀀스 S에 대해 가능한 모든 val (A, S) 값에서 val (A, S)의 최소값을 계산합니다.

예를 들어, 주어진 배열 :

   A [0] = 1
   A [1] = 5
   A [2] = 2
   A [3] = -2
S = [-1, 1, −1, 1], val (A, S) = 0이 가능한 최소값이므로 함수는 0을 반환해야합니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오.

N은 [0..20,000] 범위 내의 정수이고;
배열 A의 각 요소는 [-100..100] 범위 내의 정수입니다.

 

 

codility.com/media/train/solution-min-abs-sum.pdf

 

 

 

 

i: 1, 1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
i: 2, 2 2 1 1 0 0 -1 -1 -1 -1 -1
i: 5, 1 1 1 1 1 1 0 0 0 0 -1

 

 

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        int M = 0;
        int sum = 0;
        for(int i = 0; i < N; i++) {
            A[i] = Math.abs(A[i]);
            sum += A[i];
            M = Math.max(M, A[i]);
        }
        
        int[] count = new int[M+1];
        for(int i = 0; i < N; i++) {
            count[A[i]]++;
        }
        // for(int i = 0; i < count.length; i++) {
        //     System.out.println(count[i]);
        // }

        int[] dp = new int[sum+1];
        for(int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        dp[0] = 0;
        for(int i = 1; i < count.length; i++) {
            if(count[i] <= 0) continue;
            for(int j = 0; j < sum; j++) {
                if(dp[j] >= 0) {
                    dp[j] = count[i];
                } else if(j >= i && dp[j-i] > 0) {
                    dp[j] = dp[j-i] - 1;
                }
            }
            System.out.print("i: " + i + ",");
            for(int k = 0; k < dp.length; k++) {
                System.out.print(" " + dp[k]);
            }
            System.out.println("");
        }
        for(int i = 0; i < dp.length; i++) {
            System.out.println(dp[i]);
        }

        int result = sum;
        for(int i = 0; i < sum/2+1; i++) {
            if(dp[i] >= 0) {
                result = Math.min(result, sum-2*i);
            }
        }
        return result;
    }
}