配列分割サブ配列と近接

タイトル

記述1:無秩序で長さが偶数の正の整数配列であり、2つの長さが等しいサブ配列に分割され、この2つのサブ配列の和が最も近いことが要求される.配列の長さと対応する要素を入力し、2つのサブ配列のそれぞれの要素の和を出力します.説明2:2つの長さが等しい配列は、2つの配列の和が最も近いように要素を交換する必要がある.

試験入力1015 7 8 9 6 3 11 17

試験出力43 44

エラー解析

配列のすべての要素の和をsumとし,分割された2つのサブ配列の和を最も近づけることは,それらの和をsum 2に近づけることに相当するとし,小さなサブ配列と考えることができる.これは典型的な0-1リュックサックの問題のようで、元の問題はsum 2の大きさのリュックサックに対して、どの要素を選んでできるだけリュックサックを満たすことができるかを聞くことです.定義配列array[i],i=1〜n,s[i,j]は,前のi個の要素が総容量jのリュックサックに入る最大容量を表し,原問題はs[n,sum 2]である.第iの要素によってリュックサックを入れるかどうか、再帰式は
s[i,j]=⎧⎩⎨0,max(s[i−1,j],s[i−1,j−array[i]]+array[i]),i=0 or j=01≤i≤n,1≤j≤sum2

コード1

import java.util.Scanner;

public class ArraySplit {
    static void wrongSolution(int[] array, int[][] s, int n, int sum) {
        for (int i = 0; i < sum / 2 + 1; i++) {
            s[0][i] = 0;
        }
        s[1][0] = 0;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < sum / 2 + 1; j++) {
                int skipi = s[(i - 1) % 2][j];
                int takei = j < array[i - 1] ? 0 : 
                    s[(i - 1) % 2][j - array[i - 1]] + array[i - 1];
                s[i % 2][j] = Math.max(takei, skipi);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
            sum += array[i];
        }
        int[][] s = new int[2][sum / 2 + 1];
        solution(array, s, n, sum);
        int left = s[n % 2][sum / 2];
        System.out.println(left + " " + (sum - left));
    }
}

コードを書き終えて結果に問題があるのは、問題の1つの条件を少なくしたためであり、最も重要な条件である「2つの長さの等しいサブ配列に分割する」ことでもあり、結果が正しいのはおかしい.

正確な分析

私たちは焦って前のやり方を完全に覆すのではなく、本題と古典的な0-1リュックサックの問題にどのような違いがあるかを分析します.古典的な0-1リュックサックの問題は選択要素の個数を制限していないが、できるだけリュックサックを満たすことを要求している.本題では,リュックサックをできるだけ詰め込む前提で,選択した要素と残りの要素の個数が等しいことを要求する.このようにs[i,j]のみを用いて状態を記録することは、どれだけの要素が選択されたかを保証することはできないので、選択された要素の個数を記録するには、s[i,j,k]を定義することは、前のi要素がj個の要素を選択し、総容量kのリュックサックが占める最大容量を表すことを意味し、ここでj≦i、原問題はs[n,n 2,sum 2]である.同様にi番目の要素にリュックサックを入れるかどうかで、再帰式は
s[i,j,k]=⎧⎩⎨0,max(s[i−1,j,k],s[i−1,j−1,k−array[i]]+array[i]),i=0 or j=0 or k=01≤i≤n,1≤j≤n2,1≤k≤sum2,j≤i
これにより,0−1リュックの問題を要素個数を制限する0−1リュックの問題に拡張することに成功し,リュックの中の要素個数は総要素個数の半分に設定できるだけでなく,総個数よりも小さい任意の数であってもよい.

コード2

import java.util.Scanner;

public class ArraySplit {
    static void solution(int[] array, int[][][] s, int n, int sum) {
        for (int i = 0; i < sum / 2 + 1; i++) {
            s[0][0][i] = 0;
            s[1][0][i] = 0;
        }
        for (int i = 0; i < n / 2 + 1; i++) {
            s[0][i][0] = 0;
            s[1][i][0] = 0;
        }
        for (int i = 1; i < n + 1; i++) {
            int maxj = Math.min(i, n / 2);
            for (int j = 1; j <= maxj; j++) {
                for (int k = 1; k < sum / 2 + 1; k++) {
                    int skipi = s[(i - 1) % 2][j][k];
                    int takei = k < array[i - 1] ? 0 : 
                        s[(i - 1) % 2][j - 1][k - array[i - 1]] + array[i - 1];
                    s[i % 2][j][k] = Math.max(takei, skipi);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
            sum += array[i];
        }
        int[][][] s = new int[2][n / 2 + 1][sum / 2 + 1];
        solution(array, s, n, sum);
        int left = s[n % 2][n / 2][sum / 2];
        System.out.println(left + " " + (sum - left));
    }
}