Javaで実装するMeet in the Middle（半分全列挙）アルゴリズム ― 合計値を超えない最大部分集合和の求め方

配列と合計値が与えられたとき、「与えられた合計値を超えない最大の部分集合和」を求めるのがこの問題です。配列の構造上、単純な全探索（ブルートフォース）や一般的な分割統治法をそのまま適用することが難しいため、より効率的なアプローチが必要になります。

それでは、具体的な入出力シナリオをいくつか見ていきましょう。

具体例で理解する

入力 − long arr[] = { 21, 1, 2, 45, 9, 8 }、long given_Sum = 12

出力 − 与えられた合計値以下となる最大部分集合和 --> 12

解説 − 配列を2つの部分集合に分割します。前半には n/2 個の要素を、後半には残りの要素を割り当てます。前半部分の考えられるすべての部分集合和を計算して配列Aに格納し、同様に後半部分の部分集合和を計算して配列Bに格納します。最後に2つの部分問題の結果を統合し、合計が与えられた合計値以下となる組み合わせの中から最大値を求めます。

入力 − long arr[] = { 2, 12, 16, 25, 17, 27 }、long given_Sum = 24

出力 − 与えられた合計値以下となる最大部分集合和 --> 19

解説 − 先ほどと同じ手順で、配列を前半 n/2 個の要素と後半の要素に分割し、それぞれの部分集合和を配列A・Bに格納します。その後、2つの部分問題を統合して、合計が与えられた合計値以下となる最大の組み合わせを導き出します。

プログラムで採用しているアプローチ

• long型の配列と、合計値を格納するlong型の変数を用意し、calculateSubsetSum(arr, arr.length, given_Sum) を呼び出します。

• calculateSubsetSum(arr, arr.length, given_Sum) メソッド内部では、以下の処理を行います。

  • solve_subarray(a, A, len / 2, 0) と solve_subarray(a, B, len - len / 2, len / 2) を呼び出します。

  • AとBのサイズを計算したうえで、sort()メソッドを使用して配列Bをソートします。

  • i を 0 から配列Aのサイズ未満までループさせます。A[i] が given_Sum 以下であるかどうかを判定し、該当する場合は calculate_lower_bound(B, given_Sum - A[i]) の戻り値を get_lower_bound に設定します。get_lower_bound が size_B と等しい、または B[get_lower_bound] が (given_Sum - A[i]) と等しくない場合は、get_lower_bound を 1 減らします。

  • B[get_lower_bound] + A[i] が max より大きい場合は、max を B[get_lower_bound] + A[i] に更新します。

  • max を返します。

• solve_subarray(long a[], long x[], int n, int c) メソッド内部では、以下の処理を行います。

  • i を 0 から (1 << n) 未満までループさせます。ループ内で sum を 0 に初期化します。

  • j を 0 から n 未満までループさせます。ループ内で (i & (1 << j)) が 0 と等しい場合、sum に a[j + c] を加算します。

  • x[i] に sum を代入します。

• calculate_lower_bound(long a[], long x) メソッド内部では、以下の処理を行います。

  • left を -1、right を配列の長さとして宣言します。

  • left + 1 が right 未満である間、ループを続けます。ループ内では m を (left + right) >>> 1 として計算し、a[m] が x 以上であれば right を m に設定します。

  • そうでない場合は、left を m に設定します。

  • right を返します。

コード例

import java.util.*;
import java.lang.*;
import java.io.*;
public class testClass{
    static long A[] = new long[2000005];
    static long B[] = new long[2000005];
    static void solve_subarray(long a[], long x[], int n, int c){
        for (int i = 0; i < (1 << n); i++){
            long sum = 0;
            for (int j = 0; j < n; j++){
                if ((i & (1 << j)) == 0){
                    sum += a[j + c];
                }
            }
            x[i] = sum;
        }
    }
    static long calculateSubsetSum(long a[], int len, long given_Sum){
        solve_subarray(a, A, len / 2, 0);
        solve_subarray(a, B, len - len / 2, len / 2);
        int size_A = 1 << (len / 2);
        int size_B = 1 << (len - len / 2);
        Arrays.sort(B);
        long max = 0;
        for (int i = 0; i < size_A; i++){
            if (A[i] <= given_Sum){
                int get_lower_bound = calculate_lower_bound(B, given_Sum - A[i]);
                if (get_lower_bound == size_B || B[get_lower_bound] != (given_Sum - A[i])){
                    get_lower_bound--;
                }
                if((B[get_lower_bound] + A[i]) > max){
                    max = B[get_lower_bound] + A[i];
                }
            }
        }
        return max;
    }
    static int calculate_lower_bound(long a[], long x){
        int left = -1, right = a.length;
        while (left + 1 < right){
            int m = (left + right) >>> 1;
            if (a[m] >= x){
                right = m;
            }
            else{
                left = m;
            }
        }
        return right;
    }
    public static void main(String[] args){
        long arr[] = { 21, 1, 2, 45, 9, 8 };
        long given_Sum = 12;
        System.out.println("The maximum sum subset having sum less than or equal to the given sum-->" + calculateSubsetSum(arr, arr.length, given_Sum));
    }
}

出力

上記のコードを実行すると、次の出力が得られます。

The maximum sum subset having sum less than or equal to the given sum-->12